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

题目：

 

 

 

 

 分析：

首先理解题意：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--,g--,vis[i]=true,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,e+1+n,cmp2);
        ll ans=min(work1(),min(work2(),work3()));
        printf("%lld\n",ans);
    }
}
/*
1
4 5
1 77
3 26
3 69
1 28
*/

View Code