BZOJ1828: [Usaco2010 Mar]balloc 农场分配

1828: [Usaco2010 Mar]balloc 农场分配

Time Limit: 3 Sec Memory Limit: 32 MB
Submit: 482 Solved: 253
[Submit][Status]

Description

Input

第1行：两个用空格隔开的整数：N和M * 第2行到N+1行：第i+1行表示一个整数C_i * 第N+2到N+M+1行：第i+N+1行表示2个整数 A_i和B_i

Output

* 第一行：一个整数表示最多能够被满足的要求数

Sample Input

5 4
1
3
2
1
3
1 3
2 5
2 3
4 5

Sample Output

HINT

Source

Gold

题解：

这种选区间的问题如果范围很大一定是贪心。。。

题解戳这里：

http://blog.163.com/fjxmlhx@126/blog/static/144072841201022521659527/

http://blog.csdn.net/sdj222555/article/details/13005815

知道做法以后就是码题了。。。

代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 #define N 100005
 6 using namespace std;
 7 inline int read()
 8 {
 9     int x=0;char ch=getchar();
10     while(ch<'0'||ch>'9')ch=getchar();
11     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
12     return x;
13 }
14 int n,m,ans;
15 struct data{int l,r;}a[N];
16 struct seg{int l,r,mn,tag;}t[N*3];
17 inline bool cmp(data a,data b)
18 {return a.r<b.r;}
19 void pushdown(int k)
20 {
21      int l=t[k].l,r=t[k].r,tag=t[k].tag;
22      if(l==r||!tag)return;
23      t[k].tag=0;
24      t[k<<1].mn-=tag;t[k<<1|1].mn-=tag;
25      t[k<<1].tag+=tag;t[k<<1|1].tag+=tag;
26 }
27 void build(int k,int l,int r)
28 {
29     t[k].l=l;t[k].r=r;
30     if(l==r){t[k].mn=read();return;}
31     int mid=(l+r)>>1;
32     build(k<<1,l,mid);
33     build(k<<1|1,mid+1,r); 
34     t[k].mn=min(t[k<<1].mn,t[k<<1|1].mn);
35 }
36 bool ask(int k,int x,int y)
37 {
38      pushdown(k);
39      int l=t[k].l,r=t[k].r;
40      if(l==x&&y==r)return t[k].mn>=1;
41      int mid=(l+r)>>1;
42      if(mid>=y)return ask(k<<1,x,y);
43      else if(mid<x)return ask(k<<1|1,x,y);
44      else return (ask(k<<1,x,mid)&ask(k<<1|1,mid+1,y));
45      t[k].mn=min(t[k<<1].mn,t[k<<1|1].mn);
46 }
47 void update(int k,int x,int y)
48 {
49      pushdown(k);
50      int l=t[k].l,r=t[k].r;
51      if(l==x&&y==r){t[k].tag++;t[k].mn--;return;}
52      int mid=(l+r)>>1;
53      if(mid>=y)update(k<<1,x,y);
54      else if(mid<x)update(k<<1|1,x,y);
55      else {update(k<<1,x,mid);update(k<<1|1,mid+1,y);}
56      t[k].mn=min(t[k<<1].mn,t[k<<1|1].mn);
57 }
58 int main()
59 {
60     n=read();m=read();
61     build(1,1,n);
62     for(int i=1;i<=m;i++)
63         a[i].l=read(),a[i].r=read();
64     sort(a+1,a+m+1,cmp);
65     for(int i=1;i<=m;i++)
66         if(ask(1,a[i].l,a[i].r))
67         {
68             update(1,a[i].l,a[i].r);
69             ans++;
70         }
71     printf("%d",ans);
72     return 0;
73 }

View Code