poj_1201Intervals

Intervals

Time Limit: 2000MS	Memory Limit: 65536K
Total Submissions: 18873	Accepted: 7097

Description

You are given n closed, integer intervals [ai, bi] and n integers c1, ..., cn.

Write a program that:

reads the number of intervals, their end points and integers c1, ..., cn from the standard input,

computes the minimal size of a set Z of integers which has at least ci common elements with interval [ai, bi], for each i=1,2,...,n,

writes the answer to the standard output.

Input

The first line of the input contains an integer n (1 <= n <= 50000) -- the number of intervals. The following n lines describe the intervals. The (i+1)-th line of the input contains three integers ai, bi and ci separated by single spaces and such that 0 <= ai <= bi <= 50000 and 1 <= ci <= bi - ai+1.

Output

The output contains exactly one integer equal to the minimal size of set Z sharing at least ci elements with interval [ai, bi], for each i=1,2,...,n.

Sample Input

Sample Output

給出n個端點為整數的閉區間[ai，bi] 及相應的正整數ci，求出滿足下述條件的序列的最短長度：序列中的元素至少有ci個在第i個區間[ai，bi]中。

輸入格式

第一行n（1 ≤n ≤50000）；

接下來n行ai，bi，ci（0 ≤ai≤bi≤50000，1 ≤ci≤bi-ai+1）

輸出格式

一行L，表示序列的最短長度。

設si=序列中在區間[0，i]的元素個數，則在區間[ai，bi]中的元素個數為sbi-sai-1。

是以第i個限制條件可以用下面的不等式描述：

sbi-sai-1≥ci

問題轉化為：

求一個滿足上述條件的序列s,使sB（B=max{bi}）最小。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<cmath>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<queue>
#include <stack>
using namespace std;
#pragma warning(disable : 4996)
const int MAXN = 51000;
const int INF = 999999;

typedef struct Node 
{
	int v;//終點位置
	int value;//權值
	int next;//同一起點下在edge數組中的位置
}Node;
Node edge[MAXN * 4];//鄰接表
int first[MAXN];//以該點為起點的第一條邊在edge數組中的位置
int n; //n點數
bool visited[MAXN];
int dist[MAXN];
queue<int>Q;
int MIN, MAX;

void init()
{
	int x, y, value, index;
	memset(first, -1, sizeof(first));
	index = 1;
	MIN = INF;
	MAX = -INF;
	for (int i = 1; i <= n; i++)
	{
		scanf("%d %d %d", &x, &y, &value);
		x--;
		if(x < MIN)
		{
			MIN = x;
		}
		if(y > MAX)
		{
			MAX = y;
		}
		edge[index].v = y;
		edge[index].value = value;
		edge[index].next = first[x];
		first[x] = index++;
	}
	//cout << MIN << " " << MAX << endl;
	for (int i = MIN; i < MAX; i++)
	{
		edge[index].v = i + 1;
		edge[index].value = 0;
		edge[index].next = first[i];
		first[i] = index++;

		edge[index].v = i;
		edge[index].value = -1;
		edge[index].next = first[i + 1];
		first[i + 1] = index++;
	}
	
}


void SPFA(int Start)
{
	while (!Q.empty())
	{
		Q.pop();
	}
	for (int i = 0; i <= MAX; i++)
	{
		visited[i] = false;
		dist[i] = -INF;
	}
	dist[Start] = 0;
	visited[Start] = true;
	Q.push(Start);
	while (!Q.empty())
	{
		int top = Q.front();
		Q.pop();
		visited[top] = false;
		for (int i = first[top]; i != -1 ; i = edge[i].next)
		{
			int e = edge[i].v;
			if(dist[e] < edge[i].value + dist[top])
			{
				dist[e] = edge[i].value + dist[top];
				if(!visited[e])
				{
					Q.push(e);
					visited[e] = true;
				}
			}
		}
	}
}

int main()
{
	freopen("in.txt", "r", stdin);
	while (scanf("%d", &n) != EOF)
	{
		init();
		SPFA(MIN);
		printf("%d\n", dist[MAX]);
		//print();
	}
	return 0;
}

可以刷的題

POJ 1716

POJ 3159

POJ 1364

POJ 3169

POJ 1275

POJ 2983

轉載于:https://my.oschina.net/N3verL4nd/blog/866905