convex 凸
convave 凹
omit 省略
emit 发射，HMM发射概率

太久没写算法，Partition算法都不会写了 T_T
掌握Partition的要诀就是一点，记忆！

双向扫描版的，最后要把a[low], a[i] swap。我记忆为单向扫描了。

明天就毕业答辩了，感觉硕士三年也走到头了。

是该面对社会了

http://codeforces.com/contest/540/problem/B

这道题目，是构造型算法的贪心。

给定k个数，构造剩余的n-k个数，使得n-k个数都在[1, p],并且数组sum<=x, 并且median>=y

题解是对于剩下数，构造y，使得中位数足够，然后剩下的数都是1，也就是尽可能小，因为sum要<=x, 尽可能小，这种是尽可能小，median不用至少要这么多y才行。

因为y增加的话median一定是增长的，如果前面可以的话，后面一定可以。

int main()
{
/*
#ifndef ONLINE_JUDGE
    freopen ("in.txt" , "r" , stdin);
    freopen ("out.txt" , "w" , stdout);
#endif
*/
    int p ,x, y, n, k;
    while(cin>>n>>k>>p>>x>>y)
    {
        fill_n(a, n, 1);
        int cnt=0;
        for(int i=0;i<k;i++)
        {
            cin>>a[i];
            if(a[i]>=y) cnt++;
        }
        //int i;
        for(int i=k;i<n;i++)
        {
            if(cnt>=(n+1)/2) break;
            a[i]=y;
            cnt++;
        }
        //if(i==n) {puts("-1"); continue;}
        int sum=0;
        for(int i=0;i<n;i++) sum+=a[i];
        if(sum<=x && cnt>=(n+1)/2)
        {
            for(int i=k;i<n;i++) cout<<a[i]<<" ";
            cout<<endl;
        }
        else puts("-1");
    }
    return 0;
}

附上炮哥的一个构造算法，先满足尽可能接近sum，然后再判断中位数是否是y符合的。

int main()
{
/*
#ifndef ONLINE_JUDGE
    freopen ("in.txt" , "r" , stdin);
    freopen ("out.txt" , "w" , stdout);
#endif
*/
    int p ,x, y, n, k;
    while(cin>>n>>k>>p>>x>>y)
    {
        fill_n(a, n, 1);
        for(int i=0;i<k;i++) cin>>a[i];
        int sum=0;
        for(int i=0;i<n;i++) sum+=a[i];
        for(int i=k;i<n;i++)
        {
            if(sum+y-1>x) break;
            a[i]=y;
            sum+=y-1;
        }
        for(int i=0;i<n;i++) b[i]=a[i];
        sort(b, b+n);
        if(sum<=x && b[n/2]>=y)
        {
            for(int i=k;i<n;i++) cout<<a[i]<<" ";
            cout<<endl;
        }
        else puts("-1");
    }
    return 0;
}

炮哥，去了百度记得带我飞啊~~

Posted by richard爱闹 - 5月 30 2015
如需转载，请注明： 本文来自 Richard