題目鏈接：點擊查看

題目大意：給定一排n只奶牛，和最高的奶牛，再給出m個條件，a b表示a能看到b，問滿足條件后每只奶牛的最大高度

題目分析：a能看到b，就表示a的高度大于等于b，再加上a和b之間的高度必須小于b，所以每次操作可以讓閉區間[a+1,b-1]內的奶牛高度都減一即可簡單差分，注意記得判重

#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<cmath> #include<set> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e4+100;int a[N];set<pair<int,int> >s;int main() { // freopen("input.txt","r",stdin);int n,I,H,R;while(scanf("%d%d%d%d",&n,&I,&H,&R)!=EOF){memset(a,0,sizeof(a));s.clear();while(R--){int x,y;scanf("%d%d",&x,&y);//x和y大小不定int mmax=max(x,y);int mmin=min(x,y);if(s.insert(make_pair(mmin,mmax)).second)//用set判重{a[mmin+1]--;a[mmax]++;}}int b=H;for(int i=1;i<=n;i++){b+=a[i];printf("%d\n",b);}}return 0; }

?

總結

以上是生活随笔為你收集整理的POJ - 3263 Tallest Cow(简单差分)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。