hdu5246超级赛亚ACMer
题意（中文题意直接粘吧）
超级赛亚ACMer
Problem Description
百小度是一个ACMer，也是一个超级赛亚人，每个ACMer都有一个战斗力，包括百小度。
所谓超级赛亚人的定义，是说如果在对抗中刚好接近极限状态，那就会激发斗志，实力提升.
具体来说，就是百小度现在要接受一些ACMer的挑战了，这些ACMer有n个人，第i个人的战斗力是a[i]。
百小度接下来可以自主安排与这n个ACMer的PK顺序，他要想在PK赛中赢过另外一个ACMer，就必须使得自己的战斗力不小于对方（平局情况他会按照百小度字典上的规则把自己排在第一).
如果百小度的战斗力大于对方，那么百小度就会轻易获胜，得不到锻炼并且骄傲起来，他以后的战斗力将保持在这个值，再也不会发生改变。
如果百小度的战斗力等于对方，那么百小度在获胜的同时也会感到很吃力，但是这会激发百小度的斗志，使得他刻苦刷题，在下场PK赛之前，战斗力最多提升k点（即可以提升0~k点任意值）.
k是百小度的潜力提升上限，会被给定一个初始值，这个潜力提升上限k在后面的比赛中会下降.
每战胜一个ACMer，这个潜力上限k将减少1（因为超级赛亚人百小度也会感到累），但k最低只会减少到0，即不会出现战斗力下降的情况
。也就是第一次比赛如果激发了百小度的斗志，他能把战斗力提升0~k的任一值，如果第二次比赛继续被激发斗志，他能在第一次提升后的基础上，把战斗力再提升0 max(0,k?1),依次类推…
m是百小度的初始战斗力上限，也就是百小度第一次进行PK赛的时候，可以选择0~m的任意一个值作为他的战斗力.
现在希望你编写程序，判断一下百小度是否战胜所有的ACMer.
Input
输入包含多组数据（数据不超过500组)
第一行一个整数T，表示T组数据
对于每组数据，第一行包括三个整数n,m,k(1≤n≤104,1≤m,k≤108)
第二行包括n个正整数，表示彪形大汉的战斗力（战斗力为不超过1012的正整数）
Output
对于每组数据，先输出一行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，初始战斗力选择范围是[0,11],接下来每场战斗力提升上限是3,2,1,0,0,...,0
百小度首先使得自己的初始战斗力为10，打败战斗力为10的第一个ACMer，
然后选择战斗力提升3，变成13，打败战斗力为13的第二个ACMer，
然后选择战斗力提升2，变成15，打败战斗力为15的第三个ACMer，
之后再以任意顺序打败剩下的ACMer
思路：
不是很难的题目，我们可以这样，一开始在0-m区间找到一个最大的数a,然后在在a-a+k之间找一个最大的数b,然后在b-b+k-1之间找，然后在c-c+k-2之间找，一直找到一个无法找到的区间为止，我的想法是上面这样的，然后用三种方法实现下
（1）直接sort然后往后推（这个是最简单和最方便的方法）
（2）set找，这个还行吧
（3）然后是最麻烦的方法，用两个set一个维护左边，一个维护右边，然后用线段树处理区间问题，这样是最麻烦的，也是最慢的，交了一次超时，又交一次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 | 1
using 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;
}
最新文章
- Atitit 分区后的查询  mysql分区记录的流程与原理
- Ubuntu14.04下jdk的安装
- Evolutionary Computing: 4. Review
- svchost.exe是什么？为什么一直在运行
- python发布文件(windows)
- 剑指offer系列19--栈的压入、弹出序列
- SQL增加，删除，更改表中字段
- [Nginx 2] form表单提交，图片上传
- js一些实用例子
- SQL注入与Java
- 《深入浅出WPF》 学习笔记
- asp.net sql无限极分类实例程序
- ssh连接超时问题解决方案
- ORACLE分科目统计每科前三名的学生的语句
- MySQL 更新中国列：1366 Incorrect string value 问题解决了
- Odd-e CSD Course Day 4
- fiddler 对https支持
- 在C#用HttpWebRequest中发送GET/HTTP/HTTPS请求（转）
- vmware桥接模式无法上网
- Pytest - 进阶功能fixture