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

代碼改變世界