[USACO2010 Mar Gold 【balloc】]贪心、线段树★★

【题目链接】http://ace.delos.com/ioiupload?init=1&a=uNRSh9JKRlk
【题目】
Farmer John最近新建立了一个农场，并且正在接受奶牛的畜栏分配请求，有些
畜栏会看到农场美妙的风景。:)

农场由N (1 <= N <= 100,000) 个畜栏组成，编号为1..N，畜栏i可以最多容纳C_i只奶牛
(1 <= C_i <= 100,000)。奶牛i希望得到连续的一段畜栏，表示为一段区间 (A_i,B_i) 。
这样的话奶牛可以在这段牛棚里面转悠。(当然，这段畜栏必须要有足够的空间)

给出M (1 <= M <= 100,000) 个请求，请求出不超过畜栏承载量的情况下，最多可以满足的请求数。 考虑下面展示的一个农场： 编号 : 1 2 3 4 5
+—+—+—+—+—+
容量 : | 1 | 3 | 2 | 1 | 3 |
+—+—+—+—+—+
奶牛1 XXXXXXXXXXX (1, 3)
奶牛2 XXXXXXXXXXXXXXX (2, 5)
奶牛3 XXXXXXX (2, 3)
奶牛4 XXXXXXX (4, 5)

FJ 不能够同时满足4头奶牛的请求，否则3，4号畜栏就会有太多的奶牛。

考虑到奶牛2的请求需要一个区间包含3号和4号畜栏，我们尝试这样一种方案，让1，3，4号奶牛
的请求都得到满足，这样没有畜栏超出容量的限制，因此，对于上述情况的答案就是3，三头奶牛
(1,3,4号)的要求可以得到满足。

内存限制： 32MB

时间限制： 2S

文件名: balloc

输入格式：

* 第1行：两个用空格隔开的整数：N和M

* 第2行到N+1行：第i+1行表示一个整数C_i

* 第N+2到N+M+1行： 第i+N+1行表示2个整数 A_i和B_i

样例输入(balloc.in)

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

输出格式：

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

样例输出：(balloc.out)

3
**********************************************************************
【算法分析】
如果我们对于每个牛(l,r)的r按第一关键字增排序，l为第二关键字减排序，那么能填就填，最后能填多少就是答案。

如何证明这个贪心策略呢?
下面是我的证明。。。不知道严不严谨：
首先，假设两牛如果是包含关系，那么被包含的牛一定比包含别人的牛优。
假设这个贪心策略不是最优的，那么必然存在这样一种情况：如果填了排序后第i个牛，那么，导致了后面的j牛和k牛都不能取。而不填这第i个牛，则两人都能取。（因为这样，填i牛才是阻碍了后面的牛，导致了非最优解）
不妨设Ri1、Lj>Ri || Lk>Ri 显然不满足由于填了i牛，j牛和k牛都不能取这一题设。
2、Lj<=Li || Lk<=Li 那么，j和k中有一个牛和i是包含关系，最优性显然。
3、Li<=Lj<=Ri && Li<=Lk<=Ri 令p=max(Lj,Lk) 那么因为要让不填i牛，j牛和k牛能同时取，那么[p,Ri]这一段的最小容量必然要>=2。但是，如果满足了这个条件，那么i牛和取得p的那一只牛必然能共存，那么造成了矛盾，所以不可能。
那么，最后综上所述，上面红字的那种情况不存在。所以“这个贪心策略不是最优的”这个假设就不成立。于是，该算法最优性得证。

然后剩下的，就用线段树判断能不能填就成了。
【时间复杂度】O(m lg n + n lg n)
【空间复杂度】O(n + m)
【CODE】
/*
ID:jie22221
TASK:balloc
LANG:C++
*/
#include #include #include #include #define AA (*((Query*)A))
#define BB (*((Query*)B))
using namespace std;
const int MAXN=100005;
int n,m;
int C[MAXN];
struct Node{int l,r,Min,delta;}Tr[MAXN*3];
struct Query{int l,r;}Q[MAXN];

void init(){
cin >> n >> m;
for (int i=1;i<=n;i++) cin >> C[i];
for (int i=1;i<=m;i++)
cin >> Q[i].l >> Q[i].r;
}

int cmp(const void *A,const void *B){
if (AA.r-BB.r) return AA.r-BB.r;
return BB.l-AA.l;
}

void pushdown(int p){
Tr[p].Min-=Tr[p].delta;
if (Tr[p].l!=Tr[p].r){
Tr[p*2].delta+=Tr[p].delta;
Tr[p*2+1].delta+=Tr[p].delta;
}
Tr[p].delta=0;
}

void update(int p){
pushdown(p*2);
pushdown(p*2+1);
Tr[p].Min=min(Tr[p*2].Min,Tr[p*2+1].Min);
}

void build(int p,int l,int r){
Tr[p].l=l; Tr[p].r=r; Tr[p].delta=0;
if (l==r){
Tr[p].Min=C[l];
return;
}
int mid=(l+r) >> 1;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
update(p);
}

bool Can(int p,int l,int r){
if (r pushdown(p);
if (l<=Tr[p].l && Tr[p].r<=r) return Tr[p].Min>0;
return Can(p*2,l,r)&&Can(p*2+1,l,r);
}

void Del(int p,int l,int r){
if (r if (l<=Tr[p].l && Tr[p].r<=r){Tr[p].delta++; return;}
pushdown(p);
Del(p*2,l,r);
Del(p*2+1,l,r);
update(p);
}

void solve(){
build(1,1,n);
int ans=0;
for (int i=1;i<=m;i++)
if (Can(1,Q[i].l,Q[i].r)){
ans++;
Del(1,Q[i].l,Q[i].r);
}
cout << ans << endl;
}

int main(){
freopen("balloc.in","r",stdin);
freopen("balloc.out","w",stdout);
ios::sync_with_stdio(false);
init();
qsort(Q+1,m,sizeof(Query),cmp);
solve();
return 0;
}