首页 > ACM题库 > HDU-杭电 > HDU 3669-Cross the Wall[解题报告]HOJ
2014
11-30

HDU 3669-Cross the Wall[解题报告]HOJ

Cross the Wall

问题描述 :

“Across the Great Wall, we can reach every corner in the world!” Now the citizens of Rectland want to cross the Great Wall.
The Great Wall is a huge wall with infinite width and height, so the only way to cross is to dig holes in it. All people in Rectland can be considered as rectangles with varying width and height, and they can only dig rectangle holes in the wall. A person can pass through a hole, if and only if the person’s width and height is no more than the hole’s width and height both. To dig a hole with width W and height H, the people should pay W * H dollars. Please note that it is only permitted to dig at most K holes for security consideration, and different holes cannot overlap each other in the Great Wall. Remember when they pass through the wall, they must have their feet landed on the ground.
Given all the persons’ width and height, you are requested to find out the minimum cost for digging holes to make all the persons pass through the wall.

输入:

There are several test cases. The first line of each case contains two numbers, N (1 <= N <= 50000) and K (1 <= K <= 100), indicating the number of people and the maximum holes allowed to dig. Then N lines followed, each contains two integers wi and hi (1 <= wi, hi <= 1000000), indicating the width and height of each person.

输出:

There are several test cases. The first line of each case contains two numbers, N (1 <= N <= 50000) and K (1 <= K <= 100), indicating the number of people and the maximum holes allowed to dig. Then N lines followed, each contains two integers wi and hi (1 <= wi, hi <= 1000000), indicating the width and height of each person.

样例输入:

2 1
1 100
100 1
2 2
1 100
100 1

样例输出:

10000
200

#include <cstdio>
#include <algorithm>

using namespace std;

typedef __int64 lli;

const int N = 50000 + 10;
const int K = 100 + 10;
const lli inf = ((lli)1<<62) - 1;

struct RECT
{
	int w, h;
};

RECT person[N];
int Q[N];
lli ans[2][N];
int head, tail;

bool operator < (const RECT& a, const RECT& b)
{
	if (a.w == b.w) return a.h < b.h;
	return a.w < b.w;
}

int main()
{
	lli res;
	int n, k, s, i, j;
//	freopen("J.in", "r", stdin);
	while (scanf("%d %d", &n, &k) > 0)
	{
		if (k > n) k = n;
		for (i=0; i<n; i++) scanf("%d %d", &person[i].w, &person[i].h);
		sort(person, person + n);
		for (i=j=1; i<n; i++)
		{
			while (j > 0 && person[j-1].h <= person[i].h) j --;
			person[j++] = person[i];
		}
		n = j;
		res = inf;
		for (i=0; i<n; i++) ans[1][i] = (lli)person[i].w * person[0].h;
		if (ans[1][n-1] < res) res = ans[1][n-1];
		for (i=2,s=0; i<=k; i++,s=1-s)
		{
			head = 0;
			tail = 1;
			Q[0] = i - 2;
			for (j=i-1; j<n; j++)
			{
				while (head < tail - 1 && ans[1-s][Q[head+1]] - ans[1-s][Q[head]] < (lli)(person[Q[head]+1].h - person[Q[head+1]+1].h) * person[j].w) head ++;
				ans[s][j] = ans[1-s][Q[head]] + (lli)person[Q[head]+1].h * person[j].w;
				if (j == n - 1) break;
				while (tail > head + 1 && (person[Q[tail-1]+1].h - person[j+1].h) * (ans[1-s][Q[tail-1]] - ans[1-s][Q[tail-2]]) > (person[Q[tail-2]+1].h - person[Q[tail-1]+1].h) * (ans[1-s][j] - ans[1-s][Q[tail-1]])) tail --;
				Q[tail++] = j;
			}
			if (ans[s][n-1] < res) res = ans[s][n-1];
		}
		printf("%I64d\n", res);
	}
	return 0;
}