机房测试3:C++锦标赛(贪心)
发布时间:2020-12-16 09:13:17 所属栏目:百科 来源:网络整理
导读:题目: ? ? ? ? ?分析: 首先理解题意:zyg要和每一个人都打比赛,且只有输和赢两种情况,也就是说没打赢的人最后得分要++。 我们希望zyg打赢的人尽量地少,且rp值
题目:? ? ? ? ?分析:首先理解题意:zyg要和每一个人都打比赛,且只有输和赢两种情况,也就是说没打赢的人最后得分要++。 我们希望zyg打赢的人尽量地少,且rp值小。 先对比分大小排序,估计一下对应排名的最小分数sc,再按rp从小到大排序,然后分情况贪心: 1.使其最终得分为sc+2: 只需要打赢前sc+2个人即可,没有其他人会影响到他。 2.最终得分为sc+1: 我们担心得分为sc的人因为没有被打赢,得分+1而排在zyg前面,所以应该先处理得分为sc的人,把他们都打赢。 (同时也要打赢sc+1的人,否则按照题目要求也会在前面) 3.最终得分为sc: 思路和上面一样:先打赢sc-1的人,再打赢sc,最后为了得到sc的分,从大到小加一遍。 #include<bits/stdc++.h> using namespace std; #define ri register int #define N 2505 #define ll long long struct node{ int p; ll e; }e[N]; int read() { int x=0,fl=1; char ch=getchar(); while(ch<‘0‘||ch>‘9‘) { if(ch==‘-‘) fl=-1; ch=getchar(); } while(ch>=‘0‘&&ch<=‘9‘) x=x*10+ch-‘0‘,ch=getchar(); return x*fl; } int T,n,k,sc,vis[N],sl; bool cmp1(const node &a,const node &b) { return a.p>b.p; } bool cmp2(const node &a,const node &b) { return a.e<b.e; } ll work1() { ll tmp=0; for(ri i=1;i<=n&&i<=sc+2;++i) tmp+=e[i].e; return tmp; } ll work2() { ll tmp=0; int g=sc+1,tsl=sl; for(ri i=0;i<=n;++i) vis[i]=0; for(ri i=1;i<=n&&tsl;++i) if(e[i].p==sc+1 || e[i].p==sc) g--,tsl--,tmp+=e[i].e,vis[i]=true; for(ri i=1;i<=n&&g>0;++i) if(!vis[i]) g--,tmp+=e[i].e; return tmp; } ll work3() { ll tmp=0; int g=sc,tsl=sl,t2l=0; for(ri i=1;i<=n;++i){ vis[i]=0; if(e[i].p==sc-1) t2l++; } for(ri i=1;i<=n&&tsl;++i) if(e[i].p==sc) tsl--,g--,vis[i]=true,tmp+=e[i].e; for(ri i=1;i<=n&&t2l;++i) if(!vis[i] && (e[i].p==sc-1 ||e[i].p==sc)) t2l--,tmp+=e[i].e; for(ri i=1;i<=n&&g;++i) if(!vis[i]) g--,tmp+=e[i].e; return tmp; } bool check() { int cnt=0; for(ri i=1;i<=n;++i) if(e[i].p>n) cnt++; if(cnt>k-1) return true; return false; } int main() { freopen("tournament.in","r",stdin); freopen("tournament.out","w",stdout); T=read(); while(T--){ n=read(); k=read(); for(ri i=1;i<=n;++i) e[i].p=read(),e[i].e=read(); if(k==n+1) { printf("0n"); continue; } if(check()) { printf("-1n"); continue; } sort(e+1,e+1+n,cmp1); sc=e[k].p; sl=1; while(e[k+sl].p==e[k].p) sl++; sort(e+1,cmp2); ll ans=min(work1(),min(work2(),work3())); printf("%lldn",ans); } } /* 1 4 5 1 77 3 26 3 69 1 28 */ (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |