Intervals
| Time Limit: 2000MS |
|
Memory Limit: 65536K |
| Total Submissions: 21403 |
|
Accepted: 8053 |
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
解决方案：这题可用差分约束法，也可用线段树+贪心的方法。第二种是这样子处理的，先将每个区间按有段坐标从小到大排序，然后每从左到右选取区间进行选点，选点要从该区间右端开始选。每次先看区间已选的点有多少，然后从右端开始把不够的补上。这个过程可用线段树维护，把效率提高了。通过这道题，我对线段树的使用有了进一步的理解。
code:#include
#include
#include
#include
#define MMAX 50005 using namespace std; int sum[MMAX*4],setv[MMAX*4]; int t,_sum; struct node { int l,r,v; } line[MMAX]; bool cmp(node a,node b) { return a.r
=R&&sum[rt]&&t>=sum[rt]) { t-=sum[rt]; sum[rt]=0; return ; } if(L==R) return ; if(sum[rt]==0) { int lc=rt*2,lr=rt*2+1; sum[lr]=sum[lc]=0; } int M=(L+R)/2; if(qr>M) update(rt*2+1,M+1,R,ql,qr); if(ql<=M) update(rt*2,L,M,ql,qr); sum[rt]=sum[rt*2+1]+sum[rt*2]; } void query(int rt,int L,int R,int ql,int qr) { if(sum[rt]==0) return ; if(ql<=L&&qr>=R) { _sum+=sum[rt]; } else { if(sum[rt]==0) { int lc=rt*2,lr=rt*2+1; sum[lr]=sum[lc]=0; } int M=(L+R)/2; if(ql<=M) query(rt*2,L,M,ql,qr); if(qr>M) query(rt*2+1,M+1,R,ql,qr); } } int main() { int n; while(~scanf("%d",&n)) { memset(setv,-1,sizeof(setv)); int Max=0; for(int i=0; i