AOJ-AHU-OJ-517 序列（貪心）

序列 Time Limit: 1000 ms   Case Time Limit: 1000 ms   Memory Limit: 64 MB

Judge By Case Description 有一個整數序列，它的每個數各不相同，我們不知道它的長度是多少（即整數個數），但我們知道在某些區間中至少有多少個整數，用區間（Li,Ri,Ci）來描述，表示這個整數序列中至少有Ci個數來自區間[Li,Ri],給出若幹個這樣的區間，問這個整數序列的長度最少能為多少?

Input 第一行一個整數N（N<=1000），表示區間個數；

接下來N行，每行三個整數（Li,Ri,Ci）(0<=Li<=Ri<=1000,1<=Ci<=Ri-Li+1)，描述一個區間。

Output 僅一個數，表示該整數序列的最小長度。

Sample Input

Original

Transformed

4
4 5 1
6 10 3
7 10 3
5 6 1      

Sample Output

Original

Transformed

4      

Source IOI

————————————————————歸來的分割線———————————————————— 前言：自從去西安回來之後，放松了一個星期，一點題目都沒有做，僅僅隻是看了一點高數[窩真的害怕再次挂科鳥]。現在想一想，就算是看高數，也不能把ACM擱置，萬一撿不起來了呢？？？ 思路：這道題是一個很好的貪心題。雖然說差分限制+最短路才是正解。我WA到刷屏啊……但是這是進步。 首先，題意是對N個區間進行描述，每次描述從L到R之間至少有幾個數字存在。這N個區間有可能有交集。問最後至少存在多少個數字。 我們希望盡量多的數字是被重複描述的。因為越多的數字被重複描述，最後總的數字個數就會越少。那麼怎樣才能使數字被重複描述呢？ 聯系想到區間問題中的一個貪心——選擇盡量多的不相交區間。此類問題是先按照右端點進行從小到大排序，其原因就是自右向左的一段重疊區間是為有效長度。即這段長度是對資源（總時間）的有效消耗，想要選擇更多的區間，那就要使得有效長度盡量小。越早結束的區間就是越好的選擇。然後與更早結束的區間重疊的區間都要丢棄。 那麼這次想要使得重疊部分盡量多，能不能這麼做呢？ 隻是這次每個區間都要選，然而需要使得有效長度盡量被利用而已。首先需要一個二級排序。先按照右端點從小到大排序，這樣就可以規劃有效長度，然後如果右端點一緻，就把更長的區間放在前面，這樣就能使得有效長度最大化。

bool cmp(node a, node b)
{
	if(a.y != b.y)
		return a.y < b.y;
	else
		return a.x < b.x;
}
           

因為資料範圍很小，我們可以暴力求解。對于每一個區間，首先令其自左向右與前一個區間進行“重疊操作”，這樣就可以使得重疊部分盡量大，然後不可重疊的部分，盡量向後放，（隻要此區間盡量向後打點了，那麼下一個區間就可以盡量重疊）這樣就可以使有效長度被最大地利用。 但是，還有一個問題。那就是所謂的“至少存在幾個數字”。我描述同一個區間3次。例如： 1 3 1 1 3 2 1 3 3 那麼顯然這三句都是正确的。最後的答案必須取最大值。再例如： 1 3 1 1 4 4 顯然，操作第一個區間的時候，3打了點，1和2卻沒有打點。但是在操作第二個區間的時候，（重疊操作：）先進行統計，發現3這個數字是已經打點的，從該區間至少存在數字個數中删去了這個數字（表示重複利用），之後的打點操作會從3開始到1（重疊部分）進行打點，如果重複删去3這個數字，必然出錯。【這就是我刷屏的原因】加個continue就解決了。對于第一個“多次描述”的例子是同理的。【模拟真的是需要細心呀】 代碼如下：

/****************************************/
 #include <cstdio>
 #include <cstdlib>
 #include <cstring>
 #include <algorithm>
 #include <cmath>
 #include <stack>
 #include <queue>
 #include <vector>
 #include <map>
 #include <string>
 #include <iostream>
 using namespace std;
/****************************************/
struct node
{
	int x, y, num;
}a[1005];
bool vis[1005];

bool cmp(node a, node b)
{
	if(a.y != b.y)
		return a.y < b.y;
	else
		return a.x < b.x;
}

int main()
{
	int n;
	scanf("%d", &n);
	int ans = 0;
	int maxi = -1, mini = 2000;
	memset(vis, 0, sizeof(vis));
	for(int i = 0; i < n; i++) {
		scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].num);
		maxi = max(maxi, a[i].y);
		mini = min(mini, a[i].x);
	}
	sort(a, a+n, cmp);
	for(int k = a[0].y; a[0].num > 0; k--) {
		a[0].num--;
		vis[k] = true;//第一個區間自右向左打點
	}
	for(int i = 1; i < n; i++) {
		for(int k = a[i-1].y; k >= a[i].x; k--) {
			if(vis[k])
				a[i].num--;
		}
		for(int k = a[i].y; a[i].num > 0; k--) {
			if(vis[k])
				continue;//這一句非常重要，避免重複的删除操作
			a[i].num--;
			vis[k] = true;
		}
	}
	for(int i = mini; i <= maxi; i++) {
		if(vis[i])
			ans++;
	}
	printf("%d\n", ans);
	return 0;
}