这道题不阴险。但是做了几次才过。主要是细节问题。放代码出来给大家参考下吧。
我的解法是：
逐行处理，从第一行到最后一行都处理一次，中间跳过大片重复的数字。方法很简单。就看你是否注意细节了。

#include <stdio.h>

struct element {
	int val, len;
};

struct runlist {
	struct element ele[1024], *cur;
	int len, off;
};

struct runlist in, data[3], *line[4];
int width;

int max(int a, int b)
{
	return a > b ? a : b;
}

//#define _DBG_

#ifdef _DBG_

void rl_dump(struct runlist *rl)
{
	int i, j;

	if (!rl->len) {
		for (i = 0; i < width; i++)
			printf("--- ");
		printf("\n");
		return;
	}

	for (i = 0; i < rl->len; i++) {
		for (j = 0; j < rl->ele[i].len; j++)
			printf("%3d ", rl->ele[i].val);
	}
	printf("\n");
}

#endif

void rl_input(struct runlist *rl)
{
	int left;

	if (in.cur == &in.ele[in.len]) {
		rl->len = 0;
		return;
	}

	left = width;
	rl->len = 0;
	while (left) {
		rl->ele[rl->len].val = in.cur->val;
		if (in.cur->len - in.off > left) {
			rl->ele[rl->len].len = left;
			rl->len++;
			in.off += left;
			left = 0;
		} else {
			rl->ele[rl->len].len = in.cur->len - in.off;
			left -= rl->ele[rl->len].len;
			rl->len++;
			in.cur++;
			in.off = 0;
		}
	}

	return;
}

int out_val, out_len;

void rl_output(int val, int len)
{
#ifdef _DBG_
	printf("output %d %d\n", val, len);
#endif
	if (out_val == val) { 
		out_len += len;
		return;
	}

	if (out_val != -1) 
		printf("%d %d\n", out_val, out_len);
	out_val = val;
	out_len = len;
}

int main()
{
	int i, j, first[3], mid[3], last[3], max_first, max_mid, max_last;


	freopen("in.txt", "r", stdin);

	while (1) {
		scanf("%d", &width);
		if (!width)
			break;

		printf("%d\n", width);

		in.len = 0;
		while (1) {
			scanf("%d%d", &i, &j);
			if (!i && !j)
				break;

			in.ele[in.len].val = i;
			in.ele[in.len].len = j;
			in.len++;
		}

		
		in.cur = in.ele;
		in.off = 0;
		for (i = 0; i < 3; i++) {
			line[i] = &data[i];
			line[i]->len = 0;
		}
		rl_input(line[1]);

		out_val = -1;
		out_len = -1;

		while (1) {
			int len;

			if (!line[1]->len)
				break;

			rl_input(line[2]);
			mid[0] = mid[1] = mid[2] = -1;
			for (i = 0; i < 3; i++) {
				line[i]->cur = line[i]->ele;
				line[i]->off = 0;
			}

#ifdef _DBG_
			printf("lines\n");
			for (i = 0; i < 3; i++)
				rl_dump(line[i]);
#endif

			while (line[1]->cur - line[1]->ele != line[1]->len) {

				j = 0;
				for (i = 1; i < 3; i++)
					if (!line[j]->len && line[i]->len || 
						line[j]->len && line[i]->len &&
						line[i]->cur->len - line[i]->off <
						line[j]->cur->len - line[j]->off)
						j = i;

				len = line[j]->cur->len - line[j]->off;
#ifdef _DBG_
				printf("pick %d\n", len);
#endif

				for (i = 0; i < 3; i++)
					first[i] = mid[i];

				for (i = 0; i < 3; i++) {
					if (!line[i]->len) {
						mid[i] = -1;
						continue;
					}
					mid[i] = line[i]->cur->val;
					line[i]->off += len;
					if (line[i]->off == line[i]->cur->len) {
						line[i]->cur++;
						line[i]->off = 0;
					} 
				}

				if (line[1]->cur - line[1]->ele != line[1]->len) {
					for (i = 0; i < 3; i++)
						last[i] = line[i]->len ? line[i]->cur->val : -1;
				} else 
					last[0] = last[1] = last[2] = -1;

				max_first = max_mid = max_last = 0;
				for (i = 0; i < 3; i++) {
					if (first[i] != -1)
						max_first = max(abs(first[i] - mid[1]), max_first);
					if (mid[i] != -1)
						max_mid = max(abs(mid[i] - mid[1]), max_mid);
					if (last[i] != -1)
						max_last = max(abs(last[i] - mid[1]), max_last);
				}

				if (len == width && !max_mid && 
					in.cur->len - in.off >= width &&
					in.cur->val == mid[2]) {
					i = (in.cur->len - in.off) / width;
					rl_output(0, width * (i + 1));
					in.off += width * i;
					if (in.cur->len == in.off) {
						in.cur++;
						in.off = 0;
					}
					break;
				}

				if (len == 1) {
					max_mid = max(max_mid, max_first);
					max_mid = max(max_mid, max_last);
					rl_output(max_mid, 1);
				} else {
					rl_output(max(max_mid, max_first), 1);
					if (len > 2)
						rl_output(max_mid, len - 2);
					rl_output(max(max_mid, max_last), 1);
				} 
			}

			line[3] = line[0];
			line[0] = line[1];
			line[1] = line[2];
			line[2] = line[3];
		}

		printf("%d %d\n0 0\n", out_val, out_len);
	}

	printf("0\n");

	return 0;
}

• Re:用这方法能过 (10) DestinyDesigner 2009-03-17 22:16:26
  • Re:用这方法能过 (14) yzthz 2009-03-19 22:19:51