【2035】圆盘找数

Time Limit: 20 second
Memory Limit: 20 MB

问题描述
已知圆盘上有20个数，找出每4个相邻数中，使其相加之和最大和最小的是哪4个数，并给出他们的起始位置。

Input

输入一行20个数,空格隔开,或输入20行20个数均可,回车结束
按输入的顺序组成圆盘(输入的数为整数)。

Output

输出最大最小的和及算式,标明起始位置。(第一个数字不用场宽控制输出，其他数字场宽为2)

Sample Input

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

Sample Output

 max:16+17+18+19=70/start from:17
 min:0+ 1+ 2+ 3=6/start from:1

【题解】

在a[21..23]再复制一遍[1..3]，然后就可以用一维模拟圆盘了。

先将从i开始计算4位的连续和存入b[i]，然后找b数组中的最大值和最小值就好。数据有点坑，要优先找靠近前面的解。

场宽的设置用"%xd"

【代码】

#include <cstdio>

const int MAXN = 40;
int a[MAXN],b[MAXN],max_n,max_p,min_n,min_p;

void input_data()
{
	for (int i = 1;i <= 20;i++) 
		scanf("%d",&a[i]);
	for (int i = 1;i <= 3;i++) //从21开始复制1..3 
		a[20+i] = a[i];
	for (int i = 1;i <= 20;i++) //先初始化b数组 
		b[i] = 0;
}

void get_ans()
{
	for (int i = 1;i <= 20;i++) //计算累加和 
		for (int j = 0;j <= 3;j++)
				b[i] += a[i+j];
	max_n = b[1];max_p = 1; //最大值和最小值都置为从第一个开始 
	min_n = b[1];min_p = 1;
	for (int i = 2;i <= 20;i++) //用扫描的方式更新最优解，可以优先更新靠近左边的解。 
		{
			if (b[i] > max_n) 
				{
					max_n = b[i];
					max_p = i;	
				}
			if (b[i] < min_n)
				{
					min_n = b[i];
					min_p = i;	
				}
		}
}
	
void output_ans()
{
	printf("max:");
	printf("%d",a[max_p]); //第一个数不用设置场宽 
	for (int i = max_p+1;i <= max_p + 3;i++)
		printf("+%2d",a[i]); //场宽的格式为"%xd" 
	printf("=%d",max_n);
	printf("/start from:%d",max_p);
	
	printf("
");
	
	printf("min:");
	printf("%d",a[min_p]);
	for (int i = min_p+1;i <= min_p + 3;i++)
		printf("+%2d",a[i]);
	printf("=%d",min_n);
	printf("/start from:%d",min_p);	
}
	
int main()
{
	//freopen("F:\rush.txt","r",stdin);
	input_data();
	get_ans();
	output_ans();
	return 0;	
}