3908565_wa.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string.h>

int len[201];
int n, length;
int best[10001];

bool check(int l)
{
	int i, j, sum = 0, max = 0;

	memset(best, 0, sizeof(best));
	best[0] = 1;
	for (j = 0; j < l; j++)
	{
		sum += len[j];
		for (i = length - len[j]; i >= 0; i--)
		{
			if (best[i] == 1)
			{
				best[i + len[j]] = 1;
				if (i + len[j] > max)
					max = i + len[j];
			}
		}
	}
	return sum - max <= length;
}

int print(int l)
{
	int i, j, sum = 0, max = 0;
	int pos[10001];
	int mark[201];

	memset(mark, 0, sizeof(mark));
	memset(best, 0, sizeof(best));
	best[0] = 1;
	pos[0] = -1;
	for (j = 0; j < l; j++)
	{
		sum += len[j];
		for (i = length - len[j]; i >= 0; i--)
		{
			if (best[i] == 1 && best[i + len[j]] == 0)
			{
				best[i + len[j]] = 1;
				if (i + len[j] > max)
				{
					max = i + len[j];	
				}
				pos[i + len[j]] = j;
			}
		}
	}
	i = max;
	printf("max = %d\n", max);
	while (pos[i] != -1)
	{
		mark[pos[i]] = 1;
		i -= len[pos[i]];
	}
	for (i = 0; i < l; i++)
	{
		puts(mark[i]?"starboard":"port");
	}
	return 0;
}

int main()
{
	int sum;

	scanf("%d", &length);
	length *= 100;
	n = 0;
	sum = 0;
	while (true)
	{
		scanf("%d", &len[n]);
		if (len[n] == 0)	break;
		if (len[n] > length)	break;
		sum += len[n];
		if (sum > 2 * length)	break;
		n++;
	}
	int min, mid, max;
	min = 0;max = n;
	int ans = 0;
	while (min <= max)
	{
		mid = (min + max) >> 1;
		if (check(mid))
		{
			ans = mid;
			min = mid + 1;
		}
		else
			max = mid - 1;
	}
	printf("%d\n", ans);
	ans && print(ans);
	return 0;
}