【HDU7068】 Dota2 Pro Circuit（双端队列，模拟）

题意：

• n只队伍参加两轮比赛，给出第一轮结束后每个队的分数，以及第2论第i名能获得的分数。
• 求第i只队伍的最好名次和最差名次（允许同分名次并列）

思路：

• 对于最高排名，先给它最大的得分，再给剩下的n-1个队，去找能否让其得分<=sc，把所有的都找出来，答案就是补集。
• 对于最低排名，先给它最小的得分，在去剩下的n-1个队里找，如果得分直接比它大，那没救了直接更新，如果得分比sc小，就去分数里从大到小找，知道第一个加起来都比sc小的就用它即可。

#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
const LL maxn = 5050;
LL a[maxn], b[maxn];

LL r[maxn];
void init(LL n){for(LL i = 1; i <= n; i++)r[i]=i;}
bool cmp(LL x, LL y){ return a[x]>a[y]; }
bool cmp2(LL x, LL y){ return x>y; }

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    LL T;  cin>>T;
    while(T--){
        LL n;  cin>>n;
        for(LL i = 1; i <= n; i++)cin>>a[i];
        for(LL i = 1; i <= n; i++)cin>>b[i];
        init(n);
        sort(r+1,r+n+1,cmp);
        sort(b+1,b+n+1,cmp2);
        for(LL i = 1; i <= n; i++){
			LL hi = 0, mi = 0;
			//最高排名
            LL sc = a[i]+b[1], k = 2;  //给它最大的分
            for(LL j = n; j >= 1; j--){//得分从小到大枚举剩下的
                LL jj = r[j];
                if(jj==i)continue;
				while(a[jj]+b[k]>sc && k<=n)k++;//找得分<=sc的
				if(k<=n)hi++;					//找得到就++,让hi尽可能多
				k++;
				if(k>n)break;
            }
			hi = n-hi;//剩下的分都比它高
			//最低排名
            sc = a[i]+b[n];
            k = n-1;
            for(LL j = 1; j <= n; j++){
                LL jj = r[j];
                if(jj==i)continue;
                if(a[jj]>sc){mi++; continue;}
                else{
                    while(k>=1 && a[jj]+b[k]<=sc)k--;
                    if(k<=0)break;
                    mi++;
                    k--;
                }
            }
            cout<<hi<<" "<<mi+1<<"\n";
        }
    }
    return 0;
}



  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/119778465