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[maxn];
ll sum[maxn];//sum数组是记录了从1到i的总和
int main()
{
  ll n;
  cin >> n;
  for(ll i = 1; i <= n ; i++)
  {
    scanf("%lld",&a[i]);
  }
  sort(a+1,a+1+n);
  sum[0] = 0;
  //完成sum的赋值
  for(ll i = 1; i <= n; i++)
  {
    sum[i] = sum[i - 1] + a[i];
  }
  //对n = 1和 n = 2的情况进行特判
  if(n == 1 || n == 2)
  {
    printf("1\n");
    printf("%lld\n",a[1]);
    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[i] - sum[i - m1 - 1] + sum[n] - sum[n - m1];
      s2 = sum[i] - sum[i - m2 - 1] + sum[n] - sum[n - m2];
      if(s1 * (2 * m2 + 1) < s2 * (2 * m1 + 1)) //2 * m + 1是总个数，这个比较的是平均值得大小
      {
        l = m1 + 1;   //三分转移,从右往左看，从r处往左侧理解
      }
      else
      {
        r = m2 - 1;   //三分转移
      }
    }
    ssum = sum[i] - sum[i - l - 1] + sum[n] - sum[n - l] - (2 * l + 1) * a[i];
    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[i]);
    }
    else
    {
      printf(" %lld",a[i]);
    }
  }
  //输出后一半
  for(ll i = n - mark_len + 1; i <= n ; i++)
      printf(" %lld",a[i]);
      printf("\n");

  return 0;
}

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