acwing101. 最高的牛 【差分】
101. 最高的牛
这是一个比较典型使用差分技巧的题。
题目中给出了M对牛可以互相看见对关系，那么对于两个可以互相看到的牛a，b。在差分数组B中，只需要让
B[a+1] -= 1 B[b] += 1
这样做可以保证a，b之间的牛至少比a，b少一个高度，这样就能使得a，b可以互相看见
进过M次处理之后，就可以把差分数组转换成原始数组，原始数组还有加上最高位与原始数组上对应位的差值，也就是加上H-A[p]
因为此题的M对关系可能重复，这里我用的set进行去重复
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
const int maxn = 1e6+10;
typedef pair<int,int> pii;
int N,P,H,M;
int A[maxn],B[maxn];//高度数组，差分数组
set<pii> st;
int main(){
cin>>N>>P>>H>>M;
int a,b;
while(M--){
scanf("%d%d",&a,&b);
if(a>b) swap(a,b);
if(a!=b) st.insert({a,b});
}
for(auto p:st){
B[p.first+1]--;
B[p.second]++;
}
for(int i = 1;i<=N;i++) A[i] = A[i-1]+B[i];
for(int i = 1;i<=N;i++){
printf("%d\n",A[i]+H-A[P]);
}
return 0;
} 
查看21道真题和解析
