首页 > ACM题库 > HDU-杭电 > HDU 4071-Trick or Treat-博弈论-[解题报告]HOJ
2015
04-16

HDU 4071-Trick or Treat-博弈论-[解题报告]HOJ

Trick or Treat

问题描述 :

Johnny and his friends have decided to spend Halloween night doing the usual candy collection from the households of their village. As the village is too big for a single group to collect the candy from all houses sequentially, Johnny and his friends have decided to split up so that each of them goes to a different house, collects the candy (or wreaks havoc if the residents don’t give out candy), and returns to a meeting point arranged in advance.There are n houses in the village, the positions of which can be identified with their Cartesian coordinates on the Euclidean plane. Johnny’s gang is also made up of n people (including Johnny himself). They have decided to distribute the candy after everybody comes back with their booty. The houses might be far away, but Johnny’s interest is in eating the candy as soon as possible.Keeping in mind that, because of their response to the hospitality of some villagers, some children might be wanted by the local authorities, they have agreed to fix the meeting point by the river running through the village, which is the line y = 0. Note that there may be houses on both sides of the river, and some of the houses may be houseboats (y = 0). The walking speed of every child is 1 meter per second, and they can move along any direction on the plane.At exactly midnight, each child will knock on the door of the house he has chosen, collect the candy instantaneously, and walk back along the shortest route to the meeting point. Tell Johnny at what time he will be able to start eating the candy.

输入:

Each test case starts with a line indicating the number n of houses (1 <=n <= 50 000). The next n lines describe the positions of the houses; each of these lines contains two oating point numbers x and y (-200 000 <= x; y <=200 000), the coordinates of a house in meters. All houses are at di erent positions. A blank line follows each case. A line with n = 0 indicates the end of the input; do not write any output for this case.

输出:

Each test case starts with a line indicating the number n of houses (1 <=n <= 50 000). The next n lines describe the positions of the houses; each of these lines contains two oating point numbers x and y (-200 000 <= x; y <=200 000), the coordinates of a house in meters. All houses are at di erent positions. A blank line follows each case. A line with n = 0 indicates the end of the input; do not write any output for this case.

样例输入:

2
1.5 1.5
3 0

1
0 0

4
1 4
4 4
-3 3
2 4

5
4 7
-4 0
7 -6
-2 4
8 -5

0

样例输出:

1.500000000 1.500000000
0.000000000 0.000000000
1.000000000 5.000000000
3.136363636 7.136363636

题意:ALICE和BOB轮流买东西,ALICE的钱总数为a,BOB的钱为b,物品必须从左到右买,一次至少买一个,最先不能买的人输ALICE为先手,问谁能赢。

解法:t=a+b。只有前缀和<=t,的物品可能被买,所以之后的物品不用考虑。用ans[i]表示当前可以选择的第一个物品为i的人至少要有多少钱才可以获胜。所以面对对于最后一个可能被买的物品i,至少要有c[i]的钱才能赢。对于其他位置的物品,有两种必胜策略
1.ans[i]>=c[i]+ans[i+1],即当前选手买下第i个物品后对于第i+1个物品还处于必胜态  
2.ans[i]>=t-sum[i-1]-(ans[i+1]-1),即当前选手买下第i个物品后另一个人会处于必败态

所以最后只要判断ans[1]和a的大小关系即可

//Time:468MS	
//Memory:23860K
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 1000005;
typedef long long LL;
LL a,b,ans[MAXN],c[MAXN],sum[MAXN],t;
int n;
int main()
{
	//freopen("/home/qitaishui/code/in.txt","r",stdin);
	while(cin>>n>>a>>b)
	{
		LL tmp = 0;
		int pos=1;
		for(int i = 1; i <= n; i++)
			scanf("%d",&c[i]);
		sum[0] = 0;
		t = a+b;
		for(int i = 1; i <= n; i++)
		{
			sum[i]=sum[i-1]+c[i];
			if(sum[i]<=t) pos = i;
			else break;
		}
		//cout<<pos<<endl;
		ans[pos] = c[pos];

		for(int i = pos-1; i>0; i--)
		{
			ans[i] = min(ans[i+1]+c[i],t-sum[i-1]-(ans[i+1]-1));
		}
		if(ans[1]>a) printf("BOB\n");
		else printf("ALICE\n");
	}
	return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/tri_integral/article/details/10340761