題意（中文題意直接粘吧）
? ? ? ? ? ? ? ? ? ? ? ? ? ? 超級賽亞ACMer
Problem Description
? 百小度是一個ACMer，也是一個超級賽亞人，每個ACMer都有一個戰(zhàn)斗力，包括百小度。
所謂超級賽亞人的定義，是說如果在對抗中剛好接近極限狀態(tài)，那就會激發(fā)斗志，實力提升.


? 具體來說，就是百小度現(xiàn)在要接受一些ACMer的挑戰(zhàn)了，這些ACMer有n個人，第i個人的戰(zhàn)斗力是a[i]。




? 百小度接下來可以自主安排與這n個ACMer的PK順序，他要想在PK賽中贏過另外一個ACMer，就必須使得自己的戰(zhàn)斗力不小于對方（平局情況他會按照百小度字典上的規(guī)則把自己排在第一).


? 如果百小度的戰(zhàn)斗力大于對方，那么百小度就會輕易獲勝，得不到鍛煉并且驕傲起來，他以后的戰(zhàn)斗力將保持在這個值，再也不會發(fā)生改變。
如果百小度的戰(zhàn)斗力等于對方，那么百小度在獲勝的同時也會感到很吃力，但是這會激發(fā)百小度的斗志，使得他刻苦刷題，在下場PK賽之前，戰(zhàn)斗力最多提升k點（即可以提升0~k點任意值）.


? k是百小度的潛力提升上限，會被給定一個初始值，這個潛力提升上限k在后面的比賽中會下降.


? 每戰(zhàn)勝一個ACMer，這個潛力上限k將減少1（因為超級賽亞人百小度也會感到累），但k最低只會減少到0，即不會出現(xiàn)戰(zhàn)斗力下降的情況
。也就是第一次比賽如果激發(fā)了百小度的斗志，他能把戰(zhàn)斗力提升0~k的任一值，如果第二次比賽繼續(xù)被激發(fā)斗志，他能在第一次提升后的基礎上，把戰(zhàn)斗力再提升0 max(0,k?1),依次類推…


? m是百小度的初始戰(zhàn)斗力上限，也就是百小度第一次進行PK賽的時候，可以選擇0~m的任意一個值作為他的戰(zhàn)斗力.


? 現(xiàn)在希望你編寫程序，判斷一下百小度是否戰(zhàn)勝所有的ACMer.
?


Input
? 輸入包含多組數(shù)據(jù)（數(shù)據(jù)不超過500組)


第一行一個整數(shù)T，表示T組數(shù)據(jù)


對于每組數(shù)據(jù)，第一行包括三個整數(shù)n,m,k(1≤n≤104,1≤m,k≤108)


第二行包括n個正整數(shù)，表示彪形大漢的戰(zhàn)斗力（戰(zhàn)斗力為不超過1012的正整數(shù)）
?


Output
? 對于每組數(shù)據(jù)，先輸出一行Case #i: (1≤i≤T)


如果百小度能打敗所有的ACMer，再輸出"why am I so diao?"


否則再輸出"madan!"
?


Sample Input
2
5 11 3
15 13 10 9 8
5 11 3
8 9 10 13 16
?


Sample Output
Case #1:
why am I so diao?
Case #2:
madan!


Hint第一組樣例解釋
5個ACMer，初始戰(zhàn)斗力選擇范圍是[0,11],接下來每場戰(zhàn)斗力提升上限是3,2,1,0,0,...,0
百小度首先使得自己的初始戰(zhàn)斗力為10，打敗戰(zhàn)斗力為10的第一個ACMer，
然后選擇戰(zhàn)斗力提升3，變成13，打敗戰(zhàn)斗力為13的第二個ACMer，
然后選擇戰(zhàn)斗力提升2，變成15，打敗戰(zhàn)斗力為15的第三個ACMer，
之后再以任意順序打敗剩下的ACMer


思路：
? ? ? 不是很難的題目，我們可以這樣，一開始在0-m區(qū)間找到一個最大的數(shù)a,然后在在a-a+k之間找一個最大的數(shù)b,然后在b-b+k-1之間找，然后在c-c+k-2之間找，一直找到一個無法找到的區(qū)間為止，我的想法是上面這樣的，然后用三種方法實現(xiàn)下
（1）直接sort然后往后推（這個是最簡單和最方便的方法）
（2）set找，這個還行吧

（3）然后是最麻煩的方法，用兩個set一個維護左邊，一個維護右邊，然后用線段樹處理區(qū)間問題，這樣是最麻煩的，也是最慢的，交了一次超時，又交一次ac了，額..總之就是不是很快，寫這么多方法就是無聊寫著玩。

sort#include<stdio.h> #include<algorithm>using namespace std;__int64 num[110000];int main () {int t ,n ,cas = 1 ,i = 1;__int64 m ,k;scanf("%d" ,&t);while(t--){scanf("%d %I64d %I64d" ,&n ,&m ,&k);for(i = 1 ;i <= n ;i ++)scanf("%I64d" ,&num[i]);sort(num + 1 ,num + n + 1);__int64 now = m;num[n+1] = 100000000000000;for(i = 1 ;i <= n + 1;i ++){if(now < num[i]) break;if(now >= num[i] && now <= num[i+1]){now = num[i] + k;k --;if(k == -1) k = 0;}}printf("Case #%d:\n" ,cas ++);if(i == n + 1)printf("why am I so diao?\n");else printf("madan!\n");}return 0;}set#include<set> #include<stdio.h>using namespace std;int main () {int t ,i ,cas = 1 ,n;__int64 m ,k ,a;scanf("%d" ,&t);while(t--){scanf("%d %I64d %I64d" ,&n ,&m ,&k);set<__int64>myset;myset.clear();for(i = 1 ;i <= n ;i ++){scanf("%I64d" ,&a);myset.insert(-a);}myset.insert(0);__int64 l = -1 ,r = -m ,now;int len = myset.size();while(len--){now = *myset.lower_bound(r);if(now > l) break;myset.erase(now);l = now ,r = now - k;k -- ;if(k == -1) k = 0;}printf("Case #%d:\n" ,cas ++);if(len == 1|| *myset.lower_bound(-1000000000000000) >= r)printf("why am I so diao?\n");else printf("madan!\n");}return 0; }set1+set2+線段樹 #include<set> #include<stdio.h> #include<string.h> #include<algorithm>#define N 41000#define lson l ,mid ,t << 1 #define rson mid + 1 ,r ,t << 1 | 1using namespace std;__int64 num[N] ,tmp[N] ,Max[N]; int numn; set<__int64>L ,R;__int64 maxx(__int64 x ,__int64 y) {return x > y ? x : y; }void PushUp(int t) {Max[t] = maxx(Max[t << 1] ,Max[t << 1 | 1]); }void BuidTree(int l ,int r ,int t) {if(l == r){//scanf("%I64d" ,&Max[t]);Max[t] = num[l];return ;}int mid = (l + r) >> 1;BuidTree(lson);BuidTree(rson);PushUp(t); }void Update(int l ,int r ,int t ,int a) {if(l == r){Max[t] = 0;return ;}int mid = (l + r) >> 1;if(a <= mid) Update(lson ,a);else Update(rson ,a);PushUp(t); }__int64 Query(int l ,int r ,int t ,int a ,int b) {if(!Max[t]) return (__int64)0;if(a <= l && b >= r)return Max[t];int mid = (l + r) >> 1;__int64 m1 = 0 ,m2 = 0;if(a <= mid) m1 = Query(lson ,a ,b);if(b > mid) m2 = Query(rson ,a ,b);return maxx(m1 ,m2); }int search2(__int64 now) {int l = 1 ,r = numn ,mid ,ans;while(l <= r){mid = (l + r) >> 1;if(now >= num[mid]){ans = mid;l = mid + 1;}else r = mid - 1;}return ans; }int main () {int t ,n ,cas = 1 ,i;__int64 m ,k ,a;scanf("%d" ,&t);while(t--){scanf("%d %I64d %I64d" ,&n ,&m ,&k);for(i = 1 ;i <= n ;i ++)scanf("%I64d" ,&tmp[i]);sort(tmp + 1 ,tmp + n + 1);numn = 0;L.clear();R.clear();for(i = 1 ;i <= n ;i ++){if(i == 1 || tmp[i] != tmp[i-1]){num[++numn] = tmp[i];L.insert(tmp[i]);R.insert(-tmp[i]);}}L.insert(100000000000000);R.insert(0);BuidTree(1 ,numn ,1);int len = numn;__int64 nowl = 1 ,nowr = m ,now;while(len --){__int64 ll = *L.lower_bound(nowl);__int64 rr = -(*R.lower_bound(-nowr));//printf("%I64d %I64d***\n" ,ll ,rr);if(ll > rr) break;int lt = search2(ll);int rt = search2(rr);now = Query(1 ,numn ,1 ,lt ,rt);if(!now) break;int w = search2(now);Update(1 ,numn ,1 ,w);L.erase(now);R.erase(-now);nowl = now ,nowr = now + k;k --;if(k == -1) break;}now = Query(1 ,numn ,1 ,1 ,numn);printf("Case #%d:\n" ,cas ++);if(len == 0 || now <= nowr)printf("why am I so diao?\n");else printf("madan!\n");}return 0; }

總結

以上是生活随笔為你收集整理的hdu5246超级赛亚ACMer的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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