BAPC2014PreliminaryH 二分+贪心

题意：

给n个选手评分，你喜欢f个选手，有s个选手可以晋级，每个选手有初始分数，你有k张票，每张票都有一个分数，每个选手只能给一张票（或者不给），票必须给完。分数最高的s个选手晋级，如果你喜欢的选手跟其他选手平票了，还是算你喜欢的选手晋级。要求喜欢的选手晋级的数量最多是多少。

思路：

很容易看出是二分+贪心。

fav：喜欢的选手。nfav：其他选手。

错误想法：

如果k大于f的话，就先把分数最小的前k-f张票从小到大给从大到小的nfav。

之后进行二分，对于每个x（fav中晋级的数量），继续贪心：

如果x<f，fav中最大的x个人的分数要大于等于nfav中第s-x大的人的分数。

如果x>=f，fav中每个人的分数都要大于等于nfav中第n-x小的人的分数。

然而这样贪心是错的，在最开始分配多余的k的时候就错了，因为可能后面x<f的时候，一个nfav的最大的人很大，肯定会入选，那么给它一个最小分数的票就浪费了，给他最大分数才对。

最后还是看了数据找出来的错误QAQ

正确想法：

对于每个x（fav中被选为晋级的数量）：

票都是按分数从大到小给的。

把最大的x张票给从小到大的最大的x个fav。

如果还有票，就把票给剩下的从小到大（从大到小也可以）的fav。

如果还有票，就把票给从小到大（从大到小也可以）的最大的s-x个nfav。

如果还有票，就把票给从小到大的剩下的nfav。

检查最大的x个fav是不是大于等于第s-x大的nfav。

想一下还是有道理的，第三步就保证了我刚刚错误的贪心不会发生。

整个思路可能是这样想的：

把fav分成x个被选为要晋级的（初始分数最大的x人）和f-x个不晋级的。

把nfav分成s-x个被选为要晋级的（初始分数最大的s-x人）和n-f-(s-x)个不晋级的。

假设票按分数从大到小给，

票肯定是要先给fav的，在fav里要尽可能把票给晋级的人，而且要从小到大给，反证可以知道这样能保证x人晋级。

然后给不晋级的人，因为它们是不晋级的所以怎么给都可以。（我想的是如果给不晋级的人中大的人多一点是不是可以填补上面晋级的人出现的加了票分数也不够的情况，然而这种情况不可能发生呀，因为初始分数和票的分数都比它们小呀，所以无论是fav还是nfav，被选为晋级的人的分数肯定是要比不晋级的人的分数要大的）

再把剩下的给nfav，在nfav里要尽可能把票给晋级的人，我觉得要从小到大给啊…但是题解里说是无所谓的…emmmmm？难道不是要保证s-x个人晋级才行吗？想了一下，如果晋级人数不够的话不是更好吗，就能把名额给fav了，那么说从大到小给更好？这样的话大的人是一定要大的吧…反正这样子是小于等于s-x的人晋级就是了（当然大于是有可能的）。

然后给不晋级的人，要把票从小到大给剩下的nfav。这是为什么呢？可能会出现给票之后本是不晋级的人分数多了超过了fav中晋级的人晋级了的情况，所以要从小到大。

最后检查一下最大的x个fav的分数是不是大于等于第s-x大的nfav。

这里写的时候也有一个小技巧，可以把n-k的部分填成0，分配票的时候就更好写了，否则就一直要判断有没有票了，很麻烦。

还要注意的就是二分的下限应该是max(0,s-(n-f))，否则就会出现不合法的情况。

贪心果然难啊QAQ也证明不了自己是不是对的只能举举反例这样子QAQ

代码：

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<math.h>
#include<time.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<vector>
#include<algorithm>
#define MOD 1000000007
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
int n,s,f,k;
int fav[100010];
int nfav[100010];
int p[100010];
int curfav[100010];
int curnfav[100010];
bool judge(int x)
{
    //printf("x=%d\n",x);
    int pos=0;
    //给从小到大的最大的x个fav
    for(int i=f-x;i<f;i++)
        curfav[i]=p[pos++]+fav[i];
    //给剩下的fav
    for(int i=0;i<f-x;i++)
        curfav[i]=p[pos++]+fav[i];
    //给最大的s-x个nfav
    for(int i=n-f-(s-x);i<n-f;i++)
        curnfav[i]=p[pos++]+nfav[i];
    //给从小到大的剩下的nfav
    for(int i=0;i<n-f-(s-x);i++)
        curnfav[i]=p[pos++]+nfav[i];
    sort(curnfav,curnfav+n-f);
    /*printf("st=%d ",n-f-(s-x)-1);
    for(int i=0;i<f;i++)
        printf("%d ",curfav[i]);
    printf("\n");
    for(int i=0;i<f;i++)
        printf("%d ",curnfav[i]);
    printf("\n");*/
    //检查最大的x个fav是否大于等于第s-x大的nfav
    for(int i=f-x;i<f;i++)
        if(curfav[i]<curnfav[n-f-(s-x)-1])
            return false;
    return true;
}
int main()
{
    //freopen("/Users/apple/Downloads/preliminary/testdata/H.in","r",stdin);
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d",&n,&s,&f);
        for(int i=0;i<f;i++)
            scanf("%d",&fav[i]);
        for(int i=0;i<n-f;i++)
            scanf("%d",&nfav[i]);
        scanf("%d",&k);
        for(int i=k-1;i>=0;i--)
            scanf("%d",&p[i]);
        for(int i=k;i<n;i++)
            p[i]=0;
        sort(fav,fav+f);
        sort(nfav,nfav+n-f);
        /*for(int i=0;i<f;i++)
            printf("%d ",fav[i]);
        printf("\n");
        for(int i=0;i<n-f;i++)
            printf("%d ",nfav[i]);
        printf("\n");
        for(int i=0;i<k;i++)
            printf("%d ",p[i]);
        printf("\n");*/
        int l=max(0,s-(n-f)),r=min(s,f),ans=0;
        while(l<=r)
        {
            int mid=(l+r)>>1;
            if(judge(mid))ans=mid,l=mid+1;
            else r=mid-1;
        }
        printf("%d\n",ans);
    }
    return 0;
}


/*
 1
 10 4 5
 8 2 2 1 1
 0 2 4 7 7
 9
 3 4 4 4 4 5 5 5 5
 */