标签存档：贪心

【题目链接】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;
}

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1826
【算法分析】
如果一个x已经在缓存中，那么本次x进入就不需要再被计算。
也就是说，无论弄谁，本质上都是一样的。
而且当前这个点，必须被push进缓存。
容易得到一个贪心解法：
设当前值为x，就是按下一个x的位置前后排个序里，越后的越废。
于是只取前m个就可以了。于是可以用个二叉堆优化。
【时间复杂度】O(n lg n)
【其它】2Y。一开始把堆得del函数写错了呃@.@，因为删的不一定是第一个，写不习惯了。。
【CODE】
#include using namespace std;
const int N=105555;
struct edge{int y,next,pos;}g[N];
int n,m,e;
int a[N],lx[N],ls[N],Next[N],zz[N];

struct Heap_t{
int tot;
struct Node{int key,pos;}h[N];
void Swap(int i,int j){
Node tmp=h[i]; h[i]=h[j]; h[j]=tmp;
zz[h[i].pos]=i;
zz[h[j].pos]=j;
}
void up(int k){
while (k>1 && h[k].key>h[k/2].key){
Swap(k,k/2);
k/=2;
}
}

void down(int p){
int k;
while (p*2<=tot){
k=p*2;
if (k if (h[k].key>h[p].key){
Swap(k,p);
p=k;
}else break;
}
}

void ins(int key,int pos){
tot++;
h[tot].key=key;
h[tot].pos=pos;
zz[pos]=tot;
up(tot);
}

void del(int p){
Swap(p,tot);
zz[h[tot].pos]=0;
tot–;
up(p);
down(p);
}
}heap;

int Find(int x){
int l=1,r=n,mid;
while (l mid=(l+r)/2;
if (x>lx[mid]) l=mid+1;
else r=mid;
}
return l;
}

void init(){
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++){
scanf("%d",&a[i]);
lx[i]=a[i];
}
sort(lx+1,lx+n+1);
for (int i=1;i<=n;i++) a[i]=Find(a[i]);
for (int i=1;i<=n;i++) ls[i]=n+1;
for (int i=n;i>=1;i–){
Next[i]=ls[a[i]];
ls[a[i]]=i;
}
}

void work(){
memset(zz,0,sizeof(zz));
heap.tot=0;
int i,ans=0;
for (i=1;i<=n;i++){
if (zz[a[i]]==0){
ans++;
if (heap.tot==m) heap.del(1);
heap.ins(Next[i],a[i]);
}
else{
heap.del(zz[a[i]]);
heap.ins(Next[i],a[i]);
}
}
printf("%dn",ans);
}

int main(){
init();
work();
}

【题目大意】
给定一个括号序列，让你修改最少的次数，使之成为一个合法的括号序列。
输出这个修改次数，并输出最终字典序最小的修改后的结果。
【算法分析】
Orz。。。这类题是我最不擅长的。。。应该说直觉不够好么。。。
下面引用lcc大牛的做法：

先从左向右扫 一旦扫到一个失配的’)’就将左边第一个’）’强转‘（’ 然后反过来做一遍 这样得到的一定是最小转化而且是最小字典序

一开始我也想到个类似的，然后我居然去想，这第一个’)’会不会不能转呢。。。
= =，晕，在正向枚举的时候，stack本来就可以超过0。本就不需要考虑失配。
太SB了。。。然后就这样。
【复杂度】O(n)
【CODE】
#include #include #include const int N=1000005;
int Tc,n,ans;
int Q[N];
char S[N];

void solve1(){
int stack=0,h=1,t=0,i;
for (i=1;i<=n;i++)
if (S[i]=='(‘) stack++;
else{
Q[++t]=i;
if (!stack){
S[Q[h++]]='(‘;
ans++;
stack++;
}
else stack–;
}
}

void solve2(){
int stack=0,h=1,t=0,i;
for (i=n;i>=1;i–)
if (S[i]==’)’) stack++;
else{
Q[++t]=i;
if (!stack){
S[Q[h++]]=’)’;
ans++;
stack++;
}
else stack–;
}
}

int main(){
scanf("%d",&Tc);
for (int i=1;i<=Tc;i++){
scanf("%s",S+1);
n=strlen(S+1);
ans=0;
solve1();
solve2();
printf("Case #%d: %dn",i,ans);
puts(S+1);
}
}

【题目和数据下载地址】http://www.ut.ee/boi/
【题目大意】
给定n条电线(Ai,Bi)，其中A点都在一矩形箱子的上方，B点都在矩形箱子的下方。
其中Ai和Bi分别表示他们的横坐标。
然后这些电线交叉的话会短路，问至少要弄多少层（每层之间完全隔开），才能把这些电线全连上而又不短路。
数据保证Ai和Bi是2*n个不相同的整数。

【算法分析】
显然，假如对于一对电线(i,j)，Ai我们先对电线按Ai从小到大排序，那么就变成了求把用最少的递增数列，把这个Bi数列全部分出来。
显然，假如Bi但是N<=100000。显然很难通过，因为边都有可能超过1000 0000。
于是我们可以贪心一下。
对于每个递增序列，记录它的最后一个就可以了，因为前面的已经和扩展无关了。
然后每一次对于一个Bi，在开了的ans个递增序列里找一个这样的序列i，满足：
Max(End[i]  ：End[i]然后将Bi插到那个序列后面去。
遇过找不到这样一个序列，那么就新开一个序列，ans++，End[ans]=Bi。
最后输出ans即可。
然后对于上面那个找Max(End[i]  ：End[i]【CODE】
#include #include #include const int N=100005;
struct Point{int x,y;}a[N];
int n,ans;

struct SBT_Type{
struct Node{int l,r,key,s;}tr[N*3];
int tot,root;
void update(int p){if (p) tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+1;}
int max(int x,int y){return x>y?x:y;}

void left(int &p){
int k=tr[p].r;
tr[p].r=tr[k].l;
tr[k].l=p;
update(p);
update(k);
p=k;
}

void right(int &p){
int k=tr[p].l;
tr[p].l=tr[k].r;
tr[k].r=p;
update(p);
update(k);
p=k;
}

void repair(int &p){
if (!p) return;
bool flag=false;
if (tr[tr[tr[p].l].l].s>tr[tr[p].r].s){
right(p);
flag=true;
}
if (tr[tr[tr[p].l].r].s>tr[tr[p].r].s){
left(tr[p].l);
right(p);
flag=true;
}
if (tr[tr[tr[p].r].r].s>tr[tr[p].l].s){
left(p);
flag=true;
}
if (tr[tr[tr[p].r].l].s>tr[tr[p].l].s){
right(tr[p].r);
left(p);
flag=true;
}
if (flag){
repair(tr[p].l);
repair(tr[p].r);
repair(p);
}
}

int del(int &p,int key){
tr[p].s–;
if (key int res=tr[p].key;
if (!tr[p].l || !tr[p].r) p=tr[p].l+tr[p].r;
else tr[p].key=del(tr[p].l,0x7FFFFFFF);
return res;
}
if (key else return del(tr[p].r,key);
}

void ins(int &p,int key){
if (!p){
p=++tot;
tr[p].l=tr[p].r=0; tr[p].s=1; tr[p].key=key;
return;
}
tr[p].s++;
if (key else ins(tr[p].r,key);
repair(p);
}

int Find(int p,int key){
if (!p) return -0x7FFFFFFF;
if (key>tr[p].key) return max(tr[p].key,Find(tr[p].r,key));
return Find(tr[p].l,key);
}
}SBT;

int cmp(const void *x,const void *y){
return ((Point*)x)->x-((Point*)y)->x;
}

int main(){
freopen("pcb.in","r",stdin);
freopen("pcb.out","w",stdout);
int i,tmp;
scanf("%d",&n);
for (i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y);
qsort(a+1,n,sizeof(Point),cmp);
SBT.tot=SBT.root=ans=0;
for (i=1;i<=n;i++){
tmp=SBT.Find(SBT.root,a[i].y);
if (tmp==-0x7FFFFFFF){
ans++;
SBT.ins(SBT.root,a[i].y);
}
else{
SBT.del(SBT.root,tmp);
SBT.ins(SBT.root,a[i].y);
}
}
printf("%dn",ans);
}