Beautiful Regional Contest

Codeforces Round #604 (Div. 2)

题目链接:https://codeforces.com/contest/1265/problem/C

题目描述:

题目

思路:

1.先看输入的成绩的个数n,要满足题目要求的g>0&&s>0&&b>0&&g<b&&g<s,n/2>5,如果不满足这个条件直接判为(0 0 0)。
2.输入的数组本身就是从高分到低分的顺序,也是按照一个从高到低的顺序(用一个队列Q:特点先进先出)记录一下每个成绩和每个成绩出现的次数。
3.!!!!关键来了!!!!利用队列先进先出的特点,首先获得的是最高分的个数,最先确定金牌g的个数(为满足题意,g要小于获奖总数的1/3,也就是总人数的1/6,如果n%6==0还需再减一位;因为不要求获得金牌的数量最多,所以只需确定第一高的成绩的个数满足不满足要求即可);确定了g之后只要让s,b分别大于g即可,且只要确定了g和s,b=n/2-g-s。最后判断一下我们最终满足条件所得的g,s,b满足不满足要求即可。

代码:

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
int t,n;
struct node{
    int x,cnt;
};
const int maxn=4e5+5;
node p[maxn];
int main(){
    #ifdef HH
    freopen("G:/input.txt","r",stdin);
    #endif // HH
    scanf("%d",&t);
    while(t--){
        memset(p,0,sizeof(p));
        queue<node>Q;
        scanf("%d",&n);
        int g,s,b;
        g=s=b=0;
        int x;
        int rex,cnx;          //记录这个x出现了几次
        rex=-1;
        cnx=0;
        for(int i=1;i<=n;i++){
            scanf("%d",&x);
            if(x!=rex)p[++cnx].x=x,p[cnx].cnt=1,rex=x;
            else p[cnx].cnt++;
        }
        for(int i=1;i<=cnx;i++){
            Q.push(p[i]);
        }
        if(n/2<5){              //要保证g>0&&s>0&&b>0&&g<b&&g<s
            printf("0 0 0\n");
            continue;
        }
        while(!Q.empty()){
            node now;
            now=Q.front();
            Q.pop();
            if(g+now.cnt<=n/6-(n%6==0)&&!g&&!s&&!b)g+=now.cnt;
            else if(s<=g&&!b)s+=now.cnt;
            else if(b+now.cnt<=(n/2-g-s))b+=now.cnt;
            else break;
        }
        while(!Q.empty())Q.pop();
        if(g==0||s==0||b==0||s<=g||b<=g)printf("0 0 0\n");
        else printf("%d %d %d\n",g,s,b);
    }
    return 0;
}
Last modification:December 8th, 2019 at 10:51 am
如果觉得我的文章对你有用,请随意赞赏