小蚂蚁 发表于 2021-12-27 23:53:24

codeforces 626E Simple Skewness - 三分

2017-08-02 23:12:52
writer：pprp
题目大意：给你n个数，从n个数中选取几个数，使平均数和中位数的差值最大，将选取的个数还有选取的数字找出；
算法分析：先枚举，再三分
枚举中位数，可以证明中位数一定是一个，而不是两个组成的。
三分主要用于类似于二次函数的曲线中，有极大或者极小值

代码及分析如下：
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <cstdlib>

using namespace std;
typedef long long ll;
const ll maxn = 200050;
const ll INF = 0x3f3f3f3f;

ll a;
ll sum;//sum数组是记录了从1到i的总和

int main()
{
    ll n;

    cin >> n;

    for(ll i = 1; i <= n ; i++)
    {
      scanf("%lld",&a);
    }

    sort(a+1,a+1+n);
    sum = 0;

    //完成sum的赋值
    for(ll i = 1; i <= n; i++)
    {
      sum = sum + a;
    }

    //对n = 1和 n = 2的情况进行特判
    if(n == 1 || n == 2)
    {
      printf("1\n");
      printf("%lld\n",a);
      return 0;
    }

    ll l, r; //represent left and right
    ll m1, m2; //三分之一点处的长度，和三分之二处的长度
    ll s1, s2; //分别代表m1/m2时的总和（不包括枚举的点）
    ll mark_sum = 0, mark_len = 0, mark_mid = 1;//作为标记
    ll ssum = 0, len = 0, mid = 1 ;//初始化

    //头和尾不可能所以从 2到n-1
    for(ll i = 2 ; i <= n - 1 ; i++)
    {
      l = 1;
      r = min(n-i,i-1);//看看左右两边哪个更短，r是长度不是角标
      for(ll j = 1; j <= 100; j++)//估计了一个数:100
      {
            m1 = (2 * l + r) / 3; //三分之一点到右端的距离
            m2 = (l + 2 * r + 2) / 3;//为了向上取整才加上2，三分之二点到右端的距离

            s1 = sum - sum + sum - sum;
            s2 = sum - sum + sum - sum;
            if(s1 * (2 * m2 + 1) < s2 * (2 * m1 + 1)) //2 * m + 1是总个数，这个比较的是平均值得大小
            {
                l = m1 + 1;   //三分转移,从右往左看，从r处往左侧理解
            }
            else
            {
                r = m2 - 1;   //三分转移
            }
      }
      ssum = sum - sum + sum - sum - (2 * l + 1) * a;
      len = l;//记录长度为len
      mid = i;//记录下来枚举的点的坐标
      if(ssum*(2 * mark_len + 1) > mark_sum * (2 * len + 1))//取最大值
      {
            mark_sum = ssum;
            mark_len = len;
            mark_mid = mid;
      }

    }

    //输出个数
    cout << mark_len * 2 + 1 << endl;

    //为了格式
    ll flag = 1;
    for(ll i = mark_mid - mark_len ; i <= mark_mid ; i++)//输出前一半
    {
      if(flag)
      {
            flag = 0;
            printf("%lld",a);
      }
      else
      {
            printf(" %lld",a);
      }
    }

    //输出后一半
    for(ll i = n - mark_len + 1; i <= n ; i++)
            printf(" %lld",a);
            printf("\n");



    return 0;
}很奇怪，一开始用cin ， cout来做就不行，采用printf还有scanf的时候可以，还有要用%lld
代码改变世界


https://blog.51cto.com/u_15467355/4848190
页: [1]
查看完整版本: codeforces 626E Simple Skewness - 三分