[NEERC2015] Easy Problemset

题面翻译

有 $n$ 位出题人，他们要出 $k$ 道题。他们有一定数量的难度在 $0$ 到 $45$ 之间的简单题，和无限多道难度为 $50$ 的难题。出题人依次出题，每一位出题人都会选择他剩余的简单题目中的第一道，如果这道题目的难度大于等于之前选择的所有题目的难度之和，则会采用这道题目，否则就会丢弃这道题目。如果一位出题人的所有简单题目都用完了，他就会使用难题。直到选够了 $k$ 道题目，他们才会停止选题。

题目描述

Perhaps one of the hardest problems of any ACM ICPC contest is to create a problemset with a reasonable number of easy problems. On Not Easy European Regional Contest this problem is solved as follows.

There are $n$ jury members (judges). They are numbered from $1$ to $n$ . Judge number $i$ had prepared $p_i$ easy problems before the jury meeting. Each of these problems has a hardness between $0$ and $49$ (the higher the harder). Each judge also knows a very large (say infinite) number of hard problems (their hardness is $50$) . Judges need to select $k$ problems to be used on the contest during this meeting.

They start to propose problems in the ascending order of judges numbers. The first judge takes the first problem from his list of remaining easy problems (or a hard problem, if he has already proposed all his easy problems) and proposes it. The proposed problem is selected for the contest if its hardness is greater than or equal to the total hardness of the problems selected so far, otherwise it is considered too easy. Then the second judge does the same etc. ; after the n-th judge, the first one proposes his next problem, and so on. This procedure is stopped immediately when $k$ problems are selected.

If all judges have proposed all their easy problems, but they still have selected less than $k$ problems, then they take some hard problems to complete the problemset regardless of the total hardness.

Your task is to calculate the total hardness of the problemset created by the judges.

输入格式

The first line of the input file contains the number of judges $n(2\le n\le 10)$ and the number of problems $k(8\le k\le 14)$ . The i-th of the following $n$ lines contains the description of the problems prepared by the i-th judge. It starts with $p_i(1\le p_i\le 10)$ followed by $p_i$ non negative integers between $0$ and $49$ – the hardnesses of the problems prepared by the i-th judge in the order they will be proposed.

输出格式

Output the only integer – the total hardness of the selected problems.

样例 #1

样例输入 #1

3 8
5 0 3 12 1 10
4 1 1 23 20
4 1 5 17 49

样例输出 #1

94

样例 #2

样例输入 #2

3 10
2 1 3
1 1
2 2 5

样例输出 #2

354

提示

Time limit: 1 s, Memory limit: 256 MB.

C++实现

#include<bits/stdc++.h>
using namespace std;
queue<int,list >q[20];
int n,k,sum;
int main() {
cin>>n>>k;
for(int i=1;i<=n;i++){
int m;
cin>>m;
for(int j=1;j<=m;j++){
int x;
cin>>x;
q[i].push(x);
}
}
while(k){
for(int i=1;i<=n;i++){
if(k==0) break;
if(q[i].empty()) sum+=50,k–;
else if(q[i].front()<sum) q[i].pop();
else sum+=q[i].front(),q[i].pop(),k–;
}
}
cout<<sum;
return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容