poj1201 intervals

发表于 | 分类于 | 阅读次数: |

poj1201 Intervals

题意：

给上N个区间，每个区间[li,ri]选择ni个数，求这N个区间最少要选择多少个数。

输入：

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

输出：

6

看到题的的第一眼以为是个dp，这几天dp写疯了，实际上贪心加线段树/树状数组就好了，只是贪心肯定会TLE。
对这个N个区间的r由小到大排序，每次标记的时候从右开始标记。
初始化tree数组为0，每次标记更改为1，查询求和就ok了。
附上AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include<algorithm>
#include<iostream>
#include<sstream>
#include<cstdlib>
#include<cstring>
#include<cassert>
#include<cstdio>
#include<vector>
#include<string>
#include<queue>
#include<cmath>
#include<stack>
#include<ctime>
#include<map>
#include<set>
using namespace std;
inline int read()
{
    char ch = getchar(); int x = 0, f = 1;
    while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
    while('0' <= ch && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
struct node
{
    int l,r;
    int num;
}x[50001];
int tree[200005];
bool cmp(node a,node b)
{
    return a.r<b.r;
}
void build(int l,int r,int k)
{
    if(l==r)
    {
        tree[k]=0;
        return ;
    }
    int mid=(l+r)>>1;
    build(l,mid,k*2);
    build(mid+1,r,k*2+1);
}
int sum(int x,int y,int l,int r,int k) //区间查询
{
    if(x<=l&&y>=r)
        return tree[k];
    int mid=(l+r)>>1;
    int ans=0;
    if(mid>=x)
        ans+=sum(x,y,l,mid,k<<1);
    if(y>=mid+1)
        ans+=sum(x,y,mid+1,r,k<<1|1);
    return ans;
}
int sum1(int x,int l,int r,int k)  //单点查询
{
    if(l==r)
        return tree[k];
    int mid=(l+r)>>1;
    if(x<=mid)
        return sum1(x,l,mid,k<<1);
    if(x>mid)
        return sum1(x,mid+1,r,k<<1|1);
}
void add(int x,int y,int l,int r,int k)  //标记
{
    if(l==r)
    {
        tree[k]+=y;
        return ;
    }
    int mid=(l+r)>>1;
    if(x<=mid)
        add(x,y,l,mid,k<<1);
    else
        add(x,y,mid+1,r,k<<1|1);
    tree[k]=tree[k<<1]+tree[k<<1|1];
}
int main()
{
    int n;
    n=read();
    int maxr=0;
    memset(tree,0,sizeof tree); //初始化tree数组为0
    for(int i=0;i<n;i++)
    {
        x[i].l=read()+1;  //输入区间左边界有可能是0
        x[i].r=read()+1;
        x[i].num=read();
        maxr=max(maxr,x[i].r);
    }
    sort(x,x+n,cmp);
    build(1,maxr,1);
    for(int i=0;i<n;i++)
    {
        int ans=0;
        if(x[i].num<=sum(x[i].l,x[i].r,1,maxr,1))
            continue;
        else
        {
            ans=sum(x[i].l,x[i].r,1,maxr,1);
            for(int j=x[i].r;j>=x[i].l;j--)
            {
                if(!sum1(j,1,maxr,1))
                {
                    ans++;
                    add(j,1,1,maxr,1);
                }
                if(ans==x[i].num)
                    break;
            }
        }
    }
    cout<<tree[1]<<endl;
    return 0;
}