问题 K: Little L’s rank 时间限制: 10 Sec 内存限制: 32 MB 提交: 27 解决: 7 [提交][状态][讨论版] 题目描述 Little L, with other n people participate in two contests, and some people can get a T-shirt. Little L want to know which is the best rank he may get. You will be given Little L’s first contest score.
输入 The first line contains one integer n .(0<=n<=5000)
Next line contains n integers, which means the scores that n people get in the first contest.
Next line contains n + 1 integers, which means the scores that n + 1 people get in the second contest.
Finally is an integer S, Little L’s first contest score.
we have known that if someone’s rank is better than Little L’s, his second score is not smaller than Little L. And if the sum of someone’s two scores is the same as Little L’s, he will rank before Little L.
输出 Print a number, which is the best rank that Little L may get.
样例输入 2 3 2 3 2 1 1 样例输出 3
/*假设小明第二轮分数，其他人是否满足条件，最好结果第一轮大的匹配第二轮小的*/ #include <iostream> #include <cstdio> #include <cmath> #include <cstdlib> #include <string> #include <cstring> #include <algorithm> #include <time.h> using namespace std; int n,firstScore; int a[5005],b[5005]; bool cmp(int a, int b) { return a > b; } int main() { while(~scanf("%d",&n)) { //读入数据 for(int i=0;i<n;i++) scanf("%d",a+i); for(int i=0;i<n+1;i++) scanf("%d",b+i); //读入小L第一轮分数 scanf("%d",&firstScore); //从小到大排序 sort(a,a+n); sort(b,b+n+1); //初始化排名结果(最大) int ans = n + 1; //外循环 第二轮分数 for(int i=0;i<n+1;i++) //从小的开始排 { // allScore 表示小L的总分 + b【i】最小 int allScore = firstScore + b[i]; // s 第一轮分数的末尾（倒序）的下标 **分数最大 int s = n - 1; // rnk 可能的排名情况 int rnk = n + 1; //循环第二轮 for(int j=0;j<n+1;j++) { if(j != i) //分数不会同 { //在第一轮中找到一个最小分数值大于小L的总分 while(s >= 0 && a[s] + b[j] >= allScore) s--; // 已知排名在小L前面的人，第二场的分数也不小于小L if(s>=0) { s--; //s-- （往前，前面小） rnk--; //一个人在他后面 }else{ if(j < i) // 一对一对，有缺失，不能全都符合 rnk = n + 1; break; } } } ans = min(ans, rnk);//取排名最小 } printf("%d\n",ans); } return 0; }