2014
02-17

# Plants VS Zombies

Plants VS Zombies is a popular game in the TJU ACM Team now. However, RoBa is not very good at this game, so he wants you to write a program to help him.

We take a simplified version of this game. There are N rows in your backyard, and there are N zombies want to walk through your yard to eat your brain, and exactly one zombie in each row. The only method to defense the zombies is to plant “peashooter” on the other side of the yard. However, you need T seconds to plant one peashooter. Once the peashooter is planted, it will begin to shoot at the zombies in its row. The zombies have different speed Vi and defense Di, which means that, the zombie in the i-th row need Vi second the walk though the yard, and the i-th zombie will be killed after Di second of shooting. Please note you can only plant one peashooter in each row.

Unfortunately, in some cases, for the zombies are too fast and/or too strong and/or your planting is too slow, you cannot kill all the zombies in time, so the zombies will eat your brains.

There are several test cases in the input. The first line of each test case contains two integers N (1 <= N <= 100) and T, indicating the number of rows and the time for planting one peashooter. Then N lines follow, each of which contains two integers Vi and Di.

There are several test cases in the input. The first line of each test case contains two integers N (1 <= N <= 100) and T, indicating the number of rows and the time for planting one peashooter. Then N lines follow, each of which contains two integers Vi and Di.

3 10
20 10
40 10
30 10
3 10
20 10
40 11
30 10

1 3 2
Hint
Hint: For the first case, you should plant a peashooter in the first row, then plant in the third row, then the second row.
Then all the zombies are killed just in time. For the second case, however, the zombie in second row is a little stronger, so you cannot kill all of them.


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 111
struct Node{
int v,d,index;
}node[MAXN];
int n,t;
bool flag;

int cmp(const Node &p,const Node &q){
return p.v-p.d-t<q.v-q.d-t;
}

int main(){
//  freopen("1.txt","r",stdin);
while(~scanf("%d%d",&n,&t)){
for(int i=1;i<=n;i++){
scanf("%d%d",&node[i].v,&node[i].d);
node[i].index=i;
}
sort(node+1,node+1+n,cmp);
flag=true;
int tt=t;
for(int i=1;i<=n;i++){
if(node[i].v-node[i].d-t<0){ flag=false;break; }
t+=tt;
}
if(!flag){ puts("The zombies eat your brains!");continue; }
for(int i=1;i<=n;i++){
i==1?printf("%d",node[i].index):printf(" %d",node[i].index);
}
puts("");
}
return 0;
}

1. 一开始就规定不相邻节点颜色相同，可能得不到最优解。我想个类似的算法，也不确定是否总能得到最优解：先着一个点，随机挑一个相邻点，着第二色，继续随机选一个点，但必须至少有一个边和已着点相邻，着上不同色，当然尽量不增加新色，直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢