机房测试3：C++锦标赛（贪心）

概述题目：          分析： 首先理解题意：zyg要和每一个人都打比赛，且只有输和赢两种情况，也就是说没打赢的人最后得分要++。 我们希望zyg打赢的人尽量地少，且rp值小。 先对比分大小排序，估计一下对应排名的最小分数sc，再按rp从小到大排序，然后分情况贪心： 1.使其最终得分为sc+2： 只需要打赢前sc+2个人即可，没有其他人会影响到他。 2.最终得分为sc+1： 我们担心得分为sc的 题目：

 

 

 

 

 分析：

首先理解题意：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 longstruct 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("0\n"); continue; }        if(check()) { printf("-1\n"); 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("%lld\n",ans);    }}/*14 51 773 263 691 28*/

VIEw Code 总结

以上是内存溢出为你收集整理的机房测试3：C++锦标赛（贪心）全部内容，希望文章能够帮你解决机房测试3：C++锦标赛（贪心）所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。