首页 > ACM题库 > HDU-杭电 > HDU 3678-Integer Game[解题报告]HOJ
2014
11-30

HDU 3678-Integer Game[解题报告]HOJ

Integer Game

问题描述 :

You are given a circle of numbers (it is guaranteed that the sum of all numbers will always be larger than zero), and as long as there is a negative number among them, you can perform the following operation:

Choose a negative number Y , and then change the adjacent two numbers, X and Z , to X + Y and Z + Y respectively, and after that you can change the negative number Y to a positive number – Y .

The game terminates when no negative number can be found. Since you want to play the game as long as possible, you wonder how to play the game so that the total number of operations will be maximized, or whether there’s a way to make this game such that this game never terminate.

输入:

There are multiple test cases in the input file. Each test case starts with one integer N (3<=N<=1000) , followed by N integers in the range [-1000, 1000] on the next line, describing the numbers on the circle in the clockwise direction. Two successive inputs are separated by a blank line. A single line with N = 0 indicates the end of input file.

输出:

There are multiple test cases in the input file. Each test case starts with one integer N (3<=N<=1000) , followed by N integers in the range [-1000, 1000] on the next line, describing the numbers on the circle in the clockwise direction. Two successive inputs are separated by a blank line. A single line with N = 0 indicates the end of input file.

样例输入:

3 
1 -1 1 

5 
1 2 3 4 5 

0

样例输出:

Case 1: 1 
Case 2: 0

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<algorithm>
#include<set>
#include<vector>
#include<map>
#include<complex>
using namespace std;
typedef long long lld;
#define pb push_back
#define mp make_pair
#define X first
#define Y second
lld s[2010];
int main()
{
	int n;
	int cc=1;
	while(scanf("%d",&n)!=EOF)
	{
		if(n == 0)
			break;
		lld sum=0;
		bool zero=true;
		for(int i=0;i<n;i++)
		{
			scanf("%I64d",&s[i]);
			s[i+n]=s[i];
			sum+=s[i];
			if(s[i] != 0)
				zero=false;
		}
		if(sum < 0)
		{
			printf("Case %d: -1\n",cc++);
			continue;
		}
		if(sum == 0 && !zero)
		{
			printf("Case %d: -1\n",cc++);
			continue;
		}
		lld ans=0;
		for(int i=0;i<n;i++)
		{
			lld now=0;
			for(int j=0;j<n;j++)
			{
				now+=s[i+j];
				if(now < 0)
				{
					lld x=-now/sum;
					if(x*sum != -now)
						x++;
					ans+=x;
				}
			}
		}
		printf("Case %d: %I64d\n",cc++,ans);
	}
	return 0;
}
/*
3
1 -1 1
5
1 2 3 4 5
0

 */

  1. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.

  2. a是根先忽略掉,递归子树。剩下前缀bejkcfghid和后缀jkebfghicd,分拆的原则的是每个子树前缀和后缀的节点个数是一样的,根节点出现在前缀的第一个,后缀的最后一个。根节点b出现后缀的第四个位置,则第一部分为四个节点,前缀bejk,后缀jkeb,剩下的c出现在后缀的倒数第2个,就划分为cfghi和 fghic,第3部分就为c、c

  3. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。