Description

　　FJ有N(1 <= N <= 10,000)頭奶牛，編號為1到N,站成一條直線。每頭奶牛自己的身高(正整數(shù)，秘密未知)，告訴你最高奶牛的身高H及位置I，同時告訴你R(0 <= R <= 10,000)組信息，每組信息由兩個數(shù)ai,bi組成,表示奶牛ai可以看到奶牛bi，這就意味著奶牛bi的身高至少和奶牛ai的身高一樣高，同時奶牛ai到奶牛bi之間的奶牛身高必須低于奶牛ai
　　現(xiàn)在要你求出每頭奶牛最高可能的高度，保證有解。

Input

　　第1行輸入4個空格隔開的整數(shù)N,I,H,R
　　第2到R+1行，每行兩個空格隔開的不同的整數(shù)A,B(1<=A,B<=N)，表示奶牛A能看到奶牛B

Output

　　第1到N行，每行一個整數(shù)表示每只奶牛最高可能的高度。

Sample Input

9 3 5 5
1 3
5 3
4 3
3 7
9 8

Sample Output

5
4
5
3
4
4
5
5
5

Data Constraint

Hint

解釋：如果奶牛A和奶牛B一樣高，則可以出現(xiàn)A看到B，B又看到A的情況，如果奶牛A矮于奶牛B，則只可能出現(xiàn)奶牛A看到奶牛B，奶牛B不可能看到奶牛A。
.
.
.
.
.

分析

一開始全部高度是最高高度，每輸入a看見b，那么如果a和b之間所有奶牛有一頭比a高，那么a與b之間所有奶牛全部減1。
.
.
.
.
.

程序：

#include<iostream> using namespace std; int main() {int n,tst,h,r,s[10001],x,y,p,k;cin>>n>>tst>>h>>r;for (int i=1;i<=n;i++)s[i]=h;for (int i=1;i<=r;i++){cin>>x>>y;p=x;if (x>y){k=x;x=y;y=k;}for (int j=x+1;j<=y-1;j++)if (s[j]>=s[p]){for (int k=x+1;k<=y-1;k++)s[k]--;break;}}for (int i=1;i<=n;i++)cout<<s[i]<<endl;return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/YYC-0304/p/9499955.html

總結(jié)

以上是生活随笔為你收集整理的最高的奶牛的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。