jzoj100029. 【NOIP2017提高A组模拟7.8】陪审团（贪心，排序）

Description

陪审团制度历来是司法研究中的一个热议话题，由于陪审团的成员组成会对案件最终的结果产生巨大的影响，诉讼双方往往围绕陪审团由哪些人组成这一议题激烈争夺。小 W 提出了一个甲乙双方互相制衡的陪审团成员挑选方法：假设共有 n 名候选陪审团成员，则由甲先提名 s 位候选人，再由乙在甲提名的 s 位候选人中选出 t 名，作为最终的陪审团成员。显然这里应当有n ≥ s ≥ t。假设候选人 k 对甲、乙的有利程度都可以用一个二元组(????????, ????????)来表示，????????越大说明候选人 k 对甲越有利，????????越大则对乙越有利。在此前提下，双方的目标都变得明确：甲要最大化最终陪审团 t 人的 x 之和，最小化 y之和，乙则反之。现在甲方决定聘请你为律师，并且事先得知了乙方律师的策略：乙方律师会在你提名的 s 名候选人中选出 t 名使得这 t 人的 y 值之和最大，再保证 y 值之和最大的前提下使得 x 值之和尽量小(在对乙方最有利的前提下对甲方最不利)。现在你应当慎重地提名 s 位候选人使得最终由乙方律师确定的 t 人 x 值和最大，若有多种方案，则应再使被乙方排除掉的 s-t人的 y 值和尽量大，在此基础上最大化 s 人的 x 值之和,在此基础上最小化 s 人的 y 值之和。你的当事人并不关心你提名的具体是哪些人，只要你告诉他你提名的 s 人的 x 值之和与 y 值之和。

Input

第一行包含三个整数 n,s,t。接下来 n 行，每行两个整数分别表示????????, ????????。

Output

共一行两个整数，分别为 x 值之和与 y 值之和。

Sample Input

Sample Output

7 3

Data Constraint

对于 30%的测试数据n ≤ 20
对于 50%的测试数据n ≤ 100
对于 100%的测试数据???? ≤ 100000, ????, ???? ≤ 1000000

Hint

jzoj100029. 【NOIP2017提高A组模拟7.8】陪审团（贪心，排序）

思路：

大水题，然而题面太难读懂了。。。。

（一开始读错题面差点爆0，最后悟错题意又差点改成错的）

这道题其实是一个3条件选择问题

第一优先级为乙方选中的x最大

第二优先级为乙方弃用（s-t）个人的y的和最大

第三优先级为x的和最大

我们一个一个考虑

针对第一优先级，我们先以y排一遍序

找出y最小的（s-t）的，默认选上（他们是替死鬼，不管和谁配，永远不会被a选上）

之后按x排序，选出最大的t个，同时记下这t个中最小的y，记做minx

就可以保证被乙方选到的x的和最大

下一步考虑（s-t）的y的和

我们已经有替死鬼卡着，让乙必选我们挑的那些

于是我们把剩下的再按y排序

如果y<minx，则加进去后不影响乙方的选择

我们就可以替换替死鬼

答案的话中间记录就好咯

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#define rii register int i
using namespace std;
struct pst{
    long long x,y;
}pe[100005];
//bool operator > (pst lk,pst kl)
//{
//    return lk.x<kl.x;
//}
long long ans,n,s,t;
priority_queue<long long> q;
bool cmp1(pst lk,pst kl)
{
    if(lk.y==kl.y)
    {
        return lk.x<kl.x;
    }
    return lk.y<kl.y;
}
bool cmp2(pst lk,pst kl)
{
    if(lk.x==kl.x)
    {
        return lk.y>kl.y;
    }
    return lk.x>kl.x;
}
bool cmp3(pst lk,pst kl)
{
    if(lk.y==kl.y)
    {
        return lk.x>kl.x;
    }
    return lk.y>kl.y;
}
int main()
{
    scanf("%lld%lld%lld",&n,&s,&t);
    for(rii=1;i<=n;i++)
    {
        scanf("%lld%lld",&pe[i].x,&pe[i].y);
    }
    long long ans1=0,ans2=0;
    long long del=s-t;
    sort(pe+1,pe+n+1,cmp1);
    for(rii=1;i<=del;i++)
    {
        ans1+=pe[i].x;
        ans2+=pe[i].y; 
    }
    sort(pe+1+del,pe+n+1,cmp2);
    long long minx=19260817;
    for(rii=del+1;i<=del+t;i++)
    {
        ans1+=pe[i].x;
        ans2+=pe[i].y;
        minx=min(minx,pe[i].y);
    }
    sort(pe+s+1,pe+n+1,cmp3);
    int cnt=0,head=0;
    for(rii=del+t+1;i<=n;i++)
    {
        if(pe[i].y<minx&&cnt<del)
        {
            cnt++;
            head++;
            ans1+=pe[i].x;
            ans2+=pe[i].y;
            ans1-=pe[head].x;
            ans2-=pe[head].y;
        }
    }
    printf("%lld %lld",ans1,ans2);
//    for(rii=1;i<=n;i++)
//    {
//        cout<<pe[i].y<<" ";
//    }pe[5].y
}

秒客网