洛谷P1937 [USACO10MAR]倉配置Barn Allocation

題目描述

Farmer John recently opened up a new barn and is now accepting stall allocation requests from the cows since some of the stalls have a better view of the pastures.

The barn comprises N (1 <= N <= 100,000) stalls conveniently numbered 1..N; stall i has capacity C_i cows (1 <= C_i <= 100,000). Cow i may request a contiguous interval of stalls (A_i, B_i) in which to roam (1 <= A_i <= N; A_i <= B_i <= N), i.e., the cow would like to wander among all the stalls in the range A_i..B_i (and the stalls must always have the capacity for her to wander).

Given M (1 <= M <= 100,000) stall requests, determine the maximum number of them that can be satisfied without exceeding stall

capacities.

農夫約翰最近開了一個新的牲口棚屋，并且現在接受來自奶牛的分配畜欄請求因為其中的一些畜欄有更好風景。

畜欄包括N個畜欄(1 ≤ N ≤ 100,000)，方便起見，我們把它們編號為1..N，畜欄i能容納Ci只牛(1 ≤ Ci ≤ 100,000)，第i只牛需要連續編號畜欄（從Ai到Bi）來漫步其中，

(1 ≤ Ai ≤ N; Ai ≤ Bi ≤ N)，換言之，這只牛想要在編號范圍為Ai..Bi的畜欄漫步（所有它想要畜欄必須實施為它空出位置來供它散步）

給出M個畜欄分配請求（1 ≤ M ≤ 100,000），回答最多能滿足多少只牛的要求（不增加另外畜欄）

考慮以下例子：

畜欄號:    1   2   3   4   5 +---+---+---+---+---+ 容納空間: | 1 | 3 | 2 | 1 | 3 | +---+---+---+---+---+ Cow 1 XXXXXXXXXXX (1, 3) Cow 2 XXXXXXXXXXXXXXX (2, 5) Cow 3 XXXXXXX (2, 3) Cow 4 XXXXXXX (4, 5)

約翰顯然不能滿足所有的牛，因為畜欄3，4請求太多了

經過試驗，我們發現，我們能滿足牛1，3，4需要，所以這組數據答案為3

輸入輸出格式

輸入格式：

?

第一行包括兩個以空格隔開的正整數：N,M

第二行到第N+1行：第i+1行包括一個整數：Ci

第N+2到第N+M+1行：第i+N+1 包括兩個整數Ai、Bi

?

輸出格式：

?

僅一行：能滿足的最大需要

?

輸入輸出樣例

輸入樣例#1：

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

輸出樣例#1：

3

說明

Source: USACO 2010 March Gold

Translator: @chrome01

分析：這道題其實和借教室那道題差不多，可以考慮用線段樹來維護，我們考慮一個區間是只用考慮它的最小值的，如果最小值都能滿足條件，那么肯定是能夠滿足條件的，那么怎么樣才能讓題目給定的區間不重復呢？考慮貪心，我們先按照右端點從小到大排序，再按照左端點從大到小排序，這樣可以保證區間之間盡量不要互相影響，最后先查詢最小值，再修改就好了.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>using namespace std;const int inf = 0x7ffffff;int n,m,minn[300010],flag[300010],ans;
bool flag2 = false;struct node
{int a,b;    
}e[100010];bool cmp(node x,node y)
{if (x.b != y.b)return x.b < y.b;elsereturn x.a > y.a;
}void pushup(int o)
{minn[o] = min(minn[o * 2],minn[o * 2 + 1]);
}void pushdown(int o)
{if (flag[o]){flag[o * 2] += flag[o];flag[o * 2 + 1] += flag[o];minn[o * 2] -= flag[o];minn[o * 2 + 1] -= flag[o];}flag[o] = 0;
}void build(int l,int r,int o)
{if (l == r){scanf("%d",&minn[o]);return;}int mid = (l + r) >> 1;build(l,mid,o * 2);build(mid + 1,r,o * 2 + 1);pushup(o);
}void update(int l,int r,int o,int x,int y)
{if (x <= l && r <= y){flag[o]++;minn[o]--;return;}pushdown(o);int mid = (l + r) >> 1;if (x <= mid)update(l,mid,o * 2,x,y);if (y > mid)update(mid + 1,r,o * 2 + 1,x,y);pushup(o);
}int query(int l,int r,int o,int x,int y)
{if (x <= l && r <= y)return minn[o];pushdown(o);int mid = (l + r) >> 1,res = inf;if (x <= mid)res = min(query(l,mid,o * 2,x,y),res);if (y > mid)res = min(query(mid + 1,r,o * 2 + 1,x,y),res);return res;
}int main()
{scanf("%d%d",&n,&m);build(1,n,1);for (int i = 1; i <= m; i++)scanf("%d%d",&e[i].a,&e[i].b);sort(e + 1,e + 1 + m,cmp);for (int i = 1; i <= m; i++){if (query(1,n,1,e[i].a,e[i].b) <= 0)continue;update(1,n,1,e[i].a,e[i].b);ans++;}printf("%d\n",ans);return 0;
}

?