1431?快樂排隊 題目來源：?CodeForces 基準時間限制：1?秒 空間限制：131072?KB 分值:?80?難度：5級算法題 ?收藏 ?關注

有一群人在排隊，如果某個人想排到前面去，可以花一元錢給直接站在他前面的人，然后和這個人交換位置。如果自己沒有錢了，就不能和前面的人交換。

但是呢，隊列里面的人覺得排他前面的所有人一定要比較有錢的，至少不能比他自己拿的少。否則里面就會有人生氣。站在隊頭的人一定是高興的。

現在給出一個隊列的初始狀態，問能不能調整隊列，使得里面的人都高興。

?

樣例解釋：樣例1中，隊尾的人可以和前面的人交換，變成9 10。

Input 單組測試數據。 第一行包含一個整數n?(1?≤?n?≤?200，000)，表示隊列中的人數。 第二行包含n個空格分開的整數?ai?(0?≤?ai?≤?10^9)，ai表示隊列中第i個人手上拿的錢。編號從隊尾開始。 Output 對于每一組數據如果能夠使得所有人高興輸出Happy，否則輸出Sad。 Input示例 2 11?8 2 9?8 Output示例 Happy Sad 思路：

對讀入的所有數字加上其到隊頭的距離后的結果判重即可。

但是，為什么這樣做是對的？考慮有可能造成序列不合法的數字對，必定是初始位置在前面的數值比后面的小。但是，要將這兩個數移到一起，發現前者比后者小一，才能直接判斷不合法。于是，需要把中間的數移開。假設中間的數字已經形成了合法的序列（如果不合法必定可以用同樣的方法在中間的某個位置判斷出來），如果中間的某個數字大于等于較大數，這個數字必定大于較小數，移走這個數字會給較小數加上一；如果中間的某個數字小于較大數，移走這個數字會給較大數減去一。由于中間的數字已經形成了合法的序列，滿足單調不上升，因此大于等于較大數的數字都排在前面，必定可以從大到小依次通過較小數；對于較大數同理。不斷地移走中間數的過程中，對于前后兩者之差，任意一個中間數的影響恒為減一；因為要求兩數并攏，所有中間數對兩者差的綜合影響恒為減去中間數的個數。于是就得到不合法狀態的判斷式子：存在i,j(i>j)，滿足a[i]-a[j]=i-j，其中a[k]表示隊頭起第k個數。將等式變換一下，即得：a[i]-i=a[j]-j。

注意本題中的讀入是從隊尾到隊頭的。

錯因：思路題，思路出了點問題+unique去重需要排序。

吐槽：看，來自出題人的嘲諷，(╯‵□′)╯︵┻━┻?? #include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; int num[200001]; int t,n,sum,ans[200001]; int main(){//freopen("small.in","r",stdin);///freopen("small.out","w",stdout);scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&num[i]);for(int i=1;i<=n;i++) ans[i]=num[i]+i;sort(ans+1,ans+1+n);int cnt=unique(ans+1,ans+1+n)-(ans+1);if(cnt!=n) cout<<"Sad"<<endl;else cout<<"Happy"<<endl; }

?

轉載于:https://www.cnblogs.com/cangT-Tlan/p/7510264.html

總結

以上是生活随笔為你收集整理的51 nod 1431 快乐排队的全部內容，希望文章能夠幫你解決所遇到的問題。

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