二分加一个预处理(y总)
题目描述
达尔星有 n
个强大的下级战士,编号 1∼n
。
其中第 i
名战士的战斗力为 ri
。
战士 a
可以成为战士 b
的战斗导师,当且仅当 ra>rb
且两人之间不存在矛盾。
给定每个战士的战斗力值以及战士之间存在的 k
对矛盾关系。
请你计算,每个战士可以成为多少战士的战斗导师。
输入格式
第一行包含两个整数 n
和 k
。
第二行包含 n
个整数 r1,r2,…,rn
。
接下来 k
行,每行包含两个整数 x,y
,表示战士 x
和战士 y
之间存在矛盾。同一对矛盾关系不会在输入中重复给出,即出现了 x,y
以后,后面就不会再次出现 x,y
或 y,x
。
输出格式
共一行,n
个整数,表示每个战士可以作为战斗导师的战士数量。
数据范围
前三个测试点满足,2≤n≤10
,0≤k≤10
。
所有测试点满足,2≤n≤2×105
,0≤k≤min(2×105,n(n−1)2)
,1≤ri≤109
,1≤x,y≤n
,x≠y
。
样例
输入样例:
4 2
10 4 10 15
1 2
4 3
输出样例:
0 0 1 2
算法1
C++ 代码
//找到每一个元素对应的排位
//在排位中,选择去掉比他小并且和他有冲突的人的个数
//在读入的时候可以预处理
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n,k;//n表示战士数量,k表示存在敌对关系的数量
const int N = 10e6;
int a[N];
int b[N];
int c[N];
int main()
{
cin >> n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
c[i]=a[i];
}
sort(c,c+n+1);
while(k--){
int i,j;
cin>>i>>j;
//让战斗力更高的战士,加上战斗力低的战士的数量
if(a[i]<a[j]) b[j]++;
else if(a[i]>a[j]) b[i]++;
}
//然后这里获取每一个战士的位置
//用二分的办法将获取的
for(int i=1;i<=n;i++){
int t=a[i];
int l=1,r=n;
int mid=(l+r+1)>>1;
while(l<r){
mid=(l+r)>>1;
if(c[mid]<t) l=mid+1;
else r=mid;
}
cout<<l-b[i]-1<<" ";
}
cout<<endl;
return 0;
}
我看懂了Orz