题解：CF1976C Job Interview

Jerrycyx · 2024-10-18 14:18:48 · 题解

总体思路：二分+前缀和

因为在本题中，满员与否具有二段性，即在某个人以前一定没有满员，在这个人之后一定满员，所以可以二分查找满员的位置。

这里，记程序员能力值更高的候选人为预备程序员，测试员能力值更高的人为预备测试员。

满员很好判断，对于每个位置记录它及以前预备程序员/预备测试员的人数，直接判断是否多于需求量 n 或 m，注意如果包含删去的这候选人，需要减去他的贡献。

找出程序员和测试员满员的位置以后，有以下三种情况：

• 程序员先满员，在满员的位置以前，正常累加能力值；在满员的位置之后，只累加测试员能力值。
• 测试员先满员，在满员的位置以前，正常累加能力值；在满员的位置之后，只累加程序员能力值。
• 程序员和测试员同时满员（我代码里二分得到的其实是刚超员的前一个位置，所以这种情况可能发生，当且仅当预备程序员和预备测试员的人数都刚好等于所需程序员和测试员的人数），这时直接正常累计所有人的能力值即可。

枚举删去的候选人，然后根据上述过程即可求出最后团队的总能力值，注意在计算的时候需要时刻排除删去的候选人的影响。

要实现上述操作，需要记录以下参数：

• 仅程序员能力值的前缀和 sum_prog，仅测试员能力值的前缀和 sum_test；
• 所有候选人都选择自己的强项（即预备程序员全部成为正式程序员，预备测试员全部成为正式测试员）的总能力值前缀和 sum_ok；
• 某个位置以前预备程序员的数量 cnt_prog 和预备测试员的数量 cnt_test。

注意开 long long。

#include<cstdio>
#include<algorithm>
using namespace std;

const int N=2e5+5;
int T,n,m;
int prog[N],test[N];
long long sum_prog[N],sum_test[N],sum_ok[N]; 
int cnt_prog[N],cnt_test[N];
//以上变量含义见题解内容 
//prog(rammer)程序员；test(er)测试员 

long long getsum(long long sum[],int l,int r)
{
    return sum[r]-sum[l-1];
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n+m+1;i++)
        {
            scanf("%d",&prog[i]);
            sum_prog[i]=sum_prog[i-1]+prog[i];
        }
        for(int i=1;i<=n+m+1;i++)
        {
            scanf("%d",&test[i]);
            sum_test[i]=sum_test[i-1]+test[i];
        }
        for(int i=1;i<=n+m+1;i++)
        {
            cnt_prog[i]=cnt_prog[i-1];
            cnt_test[i]=cnt_test[i-1];
            if(prog[i]>test[i]) //这个候选人是预备程序员 
            {
                cnt_prog[i]++;
                sum_ok[i]=sum_ok[i-1]+prog[i];
            }
            if(prog[i]<test[i]) //这个候选人是预备测试员 
            {
                cnt_test[i]++;
                sum_ok[i]=sum_ok[i-1]+test[i];
            }
        }

        for(int pos=1;pos<=n+m+1;pos++)
        {
            int l=0,r=n+m+1+1;
            while(l+1<r) //[1,l] ok; [r,n+m+1] exceeded
            {
                int mid=l+r>>1,prog_now=cnt_prog[mid]; //当前位置以前的预备程序员人数 
                if(prog[pos]>test[pos] && pos<=mid) prog_now--; //排除当前候选人
                if(prog_now<=n) l=mid;
                else r=mid;
            }
            int pos_prog=l;

            l=0,r=n+m+1+1;
            while(l+1<r) //[1,l] ok; [r,n+m+1] exceeded
            {
                int mid=l+r>>1,test_now=cnt_test[mid]; //当前位置以前的预备测试员人数 
                if(prog[pos]<test[pos] && pos<=mid) test_now--; //排除当前候选人
                if(test_now<=m) l=mid;
                else r=mid;
            }
            int pos_test=l;

            long long ans=0;
            if(pos_prog<pos_test) //程序员先满员，以后所有人只能当测试员 
            {
                ans=getsum(sum_ok,1,pos_prog)+getsum(sum_test,pos_prog+1,n+m+1);
                if(pos<=pos_prog) ans-=max(prog[pos],test[pos]); //排除当前候选人 
                else ans-=test[pos];
            }
            else if(pos_prog>pos_test) //测试员先满员，以后所有人只能当程序员 
            {
                ans=getsum(sum_ok,1,pos_test)+getsum(sum_prog,pos_test+1,n+m+1);
                if(pos<=pos_test) ans-=max(prog[pos],test[pos]); //排除当前候选人
                else ans-=prog[pos];
            }
            else
            {
                if(pos_prog==n+m+1) //程序员和测试员数量刚好够 
                {
                    ans=getsum(sum_ok,1,n+m+1);
                    ans-=max(prog[pos],test[pos]);
                }
                else return -1; //为了防止出现意想不到的情况
                //上面的 if/else 语句可以删去，只保留中间的处理部分 
            }
            printf("%lld ",ans);
        }
        putchar('\n');
    }
    return 0;
}