本文主要是介绍codeforces 412 D Dynamic Problem Scoring，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：两个人比赛，得分规则如下：
每个题目的分值如下，
其中的分数代表，解决这道题目的人数占总比赛人数的比例；
每个人可以得的分数如下： 题目分值*（1-此人解决这道题目所用时间/250）；
在比赛的所有的人当中有两个人，其中一个人的编号为0，名字为Vasya，另一个编号为1 ，名字为Petya,现在vasya想得到比petya高的分数，他申请了很多个账号来交题，他可以用申请的账号来交他做出来的题目，他没有做出来的题目不能交，现在给出n个人，其中包括vasya和petya，给出每个人解决题目所用的时间，其中一共有5道题目，现在问patya最少需要申请多少个账号可以得到比petya的分数高，如果vasya的分数不能比petya的高输出-1，否则输出所申请的账号数量。
思路：枚举+贪心
枚举：先统计现在每个题目过题的人数，然后在求进入下一档次时所有人的人数。因为每个题目的分值相当于是一个区间，每个分值有一个区间，所以枚举每个题目进入下一个档次所有人的数量。
贪心：为了让vasya的分数比petya的分数高并且需要申请账号的数量进可能的少，有如下贪心策略
- 当vasya没过这个题的时候，此时其他账号也不能过这个题，此时过了这个题目的人数等于原人数
- 当vasya过了这个题并且petya没过这个题的时候，要让分数尽可能的高，所以此时过题的人数等于原人数
- 当vasya题的时间比petya短时，要让这个题目的分数尽可能的高，所以此时过题人数等于原人数
- 当vasya过题的时间比prtya高的时候，要让这个题目的分值尽可能的低，所以此时过题人数等于原过题人数加上现在又加上的人数
代码如下
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cstdio>
#include <vector>using namespace std;
int per[200][5];
int num[5];
int n;
int getscore(int idx,bool is,int nn)
{if(per[is][idx]==-1) return 0;int solved=0;if(per[0][idx]==-1||per[1][idx]==-1||per[0][idx]<=per[1][idx]){solved=num[idx];}else{solved=nn-n+num[idx];}int maxn=500;for(int i=2; i<=32; i*=2){if(solved*i>nn) break;else maxn+=500;}return maxn*(1.0-per[is][idx]/250.0);
}
int main()
{scanf("%d",&n);memset(num,0,sizeof(num));memset(per,0,sizeof(per));for(int i=0; i<n; i++){for(int j=0; j<5; j++){scanf("%d",&per[i][j]);if(per[i][j]!=-1) num[j]++;}}vector<int> v;v.clear();v.push_back(n);for(int i=0; i<5; i++){for(int j=2; j<=32; j*=2)if(num[i]*j>=n) v.push_back(num[i]*j);}sort(v.begin(),v.end());for(int i=0; i<v.size(); i++){if(i&&v[i]==v[i-1]) continue;int score1=0,score2=0;for(int j=0; j<5; j++)score1+=getscore(j,false,v[i]);for(int j=0; j<5; j++)score2+=getscore(j,true,v[i]);if(score1>score2){cout<<v[i]-n<<endl;return 0;}}cout<<-1<<endl;return 0;
}
这篇关于codeforces 412 D Dynamic Problem Scoring的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
