Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

测试了N多数据都未发现错误,狂郁闷中...哪位牛大侠可否帮忙看下,到底是哪里出错了,不胜感激 或者是给出一组有问题的测试数据也行

Posted by wilxy at 2008-03-16 14:33:28 on Problem 1230
#include <iostream>
//#include <algorithm>
//#include <fstream>
using namespace std;

struct Col
{
	int value;
	int row;
};

struct Grid
{
	int value;
	int wall;
};

int QSCore(struct Col L[], int left, int right)
{
	int base = L[left].value;
	int temp = L[left].row;
	while (left < right)
	{
		while (L[right].value >= base && right > left) right--;
		L[left].value = L[right].value;
		L[left].row = L[right].row;
		while (L[left].value <= base && left < right) left++;
		L[right].value = L[left].value;
		L[right].row = L[left].row;
	}
	L[left].value = base;
	L[left].row = temp;
	return left;
}

void QS(struct Col L[], int left, int right)
{
	int middle;
	if (right > left)
	{
		middle = QSCore(L, left, right);
		QS(L, left, middle - 1);
		QS(L, middle + 1, right);
	}
}


int main()
{
	//data definition
	int t, n, k;
	struct Grid grid[120][120];
	int pass[120];
	struct Col col[120];
	int i, j, p, q, u, w, int_temp;
	int beginX, endX, beginY, endY;
	int maxX, maxY;
	int count;

	//input data
	//ifstream input("data.txt");
	cin >> t;
	for (w = 0; w < t; w++)
	{
		count = 0;
		cin >> n >> k;
		maxX = 0;
		maxY = 0;
		for (i = 0; i < 101; i++)
			for (j = 0; j < 101; j++)
			{
				grid[i][j].value = 0;
				grid[i][j].wall = -1;
			}
		for (i = 0; i < n; i++)
		{
			cin >> beginX >> beginY >> endX >> endY;
			if (beginX > endX) 
			{
				int_temp = beginX;
				beginX = endX;
				endX = beginX;
			}
			if (endX > maxX) maxX = endX;
			if (endY > maxY) maxY = endY;
			for (j = beginX; j <= endX; j++)
			{
				grid[endY][j].value = 1;
				grid[endY][j].wall = i;
			}
		}

		//scan grid to get value of pass
		for (i = 0; i <= maxX; i++)
		{
			pass[i] = 0;
			for (j = 0; j <= maxY; j++)
			{
				if (grid[j][i].value == 1) pass[i]++;
			}
		}

		//scan grid again
		for (i = 0; i <= maxX; i++)
		{
			if (pass[i] <= k) continue;
			for (j = 0; j <= maxY; j++)
			{
				col[j].row = j;
				if (grid[j][i].value == 0) col[j].value = 0;
				else
				{
					col[j].value = 1;
					for (p = i + 1; p <= maxX; p++)
					{
						if (grid[j][p].value == 1 && grid[j][p].wall == grid[j][i].wall) col[j].value++;
						else break;
					}
				}
			}

			QS(col, 0, maxY);

			for (p = maxY, j = pass[i]; j > k && p >= 0; j--, p--)
			{
				u = i + 1;
				q = col[p].row;
				while (grid[q][u].value == 1 && u <= maxX && grid[q][u].wall == grid[q][i].wall)
				{
					grid[q][u].value = 0;
					grid[q][u].wall = -1;
					pass[u]--;
					u++;
				}
				count++;		
			}
		}
		cout << count << endl;
	}
	return 0;
}

思路是这样子的:
>把所有点都用grid[][]记录,value值是墙为1,非墙为0;wall值记录属于哪一条墙的,若无墙则为-1
>从左往右遍历,
>如遇某列超出K了,假设超出M个
>在该列上选取对后面影响最大的M条墙,去除后
>继续遍历.
>去掉多少条墙,就是答案了。

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator