首页 > 代码库 > poj 1201 Intervals（差分约束）

poj 1201 Intervals（差分约束）

2024-07-08 15:50:08   232人阅读

Intervals
Time Limit: 2000MS Memory Limit: 65536K
Total Submissions: 20775 Accepted: 7859

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

5
3 7 3
8 10 3
6 8 1
1 3 1
10 11 1

Sample Output

6
题意：告诉你n个区间，要在第i区间至少取ci个数，问所有区间总共至少去多少个数？
这题的构图很是巧妙，把每个边界看成节点，Xi表示0-i有多少个数被选上，则每个区间[li,ri]可以推出X[ri]-X[li-1]>=Ci，即：X[li-1]-X[ri]<=-Ci。
潜在不等式：
1、X[i]-X[i+1]<=0;
2、X[i+1]-X[i]<=0.
本题我多了一个离散化操作。
#include <iostream>
#include <cstdio>
#include <map>
#include <queue>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

const int INF = 0x3f3f3f3f;
const int maxn = 2000100;
struct edge{
    int u , v , d;
    edge(int a = 0 , int b = 0 , int c = 0){
        u = a , v = b , d = c;
    }
}e[maxn];
int head[maxn] , next[maxn] , cnt , n;
int dis[maxn] , vis[maxn] , vt[maxn] , index;
map<int , int> mp;
struct interval{
    int l , r , value;
    interval(int a = 0 , int b = 0 , int c = 0){
        l = a , r = b , value = http://www.mamicode.com/c;>































        

            
                
                  
                
                

                    联系

                    我们