1 条题解
-
4
对于每一个当前处理的队伍 ,显然它应该赢,设其分数为 。
接下来分类讨论所有其他比赛:
让我们化身 【数据删除】 贪心的操纵比赛。
设 分别是一场比赛中双方在比赛开始前的得分()。
若 显然可以令两者打平不对 造成影响。
若 应该令 获胜。若 比 大的数量加一。
若 随便令其中一个获胜,答案加一。
若 分数太多操控也没用,答案加二。
但是暴力相加是不优的,注意到最后一类可以预处理,三四类有一个共同特点是右端点是 m,直接在预处理的时候开桶计算,前两类没有贡献直接忽视。
#include<bits/stdc++.h> #define int long long using namespace std; const int N=2e5+19; int a[N],n,b[N]; int t[N*3]; signed main(){ freopen("football.in","r",stdin); freopen("football.out","w",stdout); cin >> n; for(int i=1;i<=n*2;i++){ cin >> a[i];b[i]=a[i]; }sort(b+1,b+n+n+1); for(int i=1;i<=n;i++){ int x,y;cin>>x>>y; x++,y++; if(a[x]>a[y]) swap(x,y); if(a[y]-2<=a[x]&&a[x]<=a[y]){ t[a[y]]++; } } for(int i=1;i<=n*2;i++){ int ct=upper_bound(b+1,b+n+n+1,a[i]+3)-b-1; //cout << ct << "()\n"; int ans=n+n-ct+1+t[a[i]+3]; cout << ans << ' '; } return 0; }
- 1
信息
- ID
- 962
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- (无)
- 递交数
- 31
- 已通过
- 11
- 上传者