首页 > 代码库 > BZOJ1828: [Usaco2010 Mar]balloc 农场分配

BZOJ1828: [Usaco2010 Mar]balloc 农场分配

2024-07-27 17:40:59   220人阅读

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

3

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

 

BZOJ1828: [Usaco2010 Mar]balloc 农场分配


联系
我们