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

3 2 1 2 1 3 4 5 2

Sample Output

7 3?

Data Constraint

對于 30%的測試數據n ≤ 20
對于 50%的測試數據n ≤ 100
對于 100%的測試數據? ≤ 100000, ?, ? ≤ 1000000

Hint

思路：

大水題，然而題面太難讀懂了。。。。

（一開始讀錯題面差點爆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 }

?

轉載于:https://www.cnblogs.com/ztz11/p/9493404.html

總結

以上是生活随笔為你收集整理的jzoj100029. 【NOIP2017提高A组模拟7.8】陪审团（贪心，排序）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。