bzoj1745[Usaco2005 oct]Flying Right 飞行航班*
2024-10-09 10:39:57
bzoj1745[Usaco2005 oct]Flying Right 飞行航班
题意:
n个农场,有k群牛要从一个农场到另一个农场(每群由一只或几只奶牛组成)飞机白天从农场1到农场n,晚上从农场n到农场1,上面有c个座位,问最多可以满足多少只牛的要求。n≤10000,k≤50000,c≤100。
题解:
用类似贪心的方法做,现将每个农场出发的牛组织成链表。先求早上:当飞机到达每个农场时,先让到达的奶牛下机,接着如果飞机未满,则将其填满,之后枚举剩下的奶牛,如果它们的目的地比坐在飞机上面的奶牛目的地近,就将其替换为当前奶牛,这一过程可以用multiset维护。晚上所有过程都倒过来再做一次即可。
代码:
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 10010
using namespace std; inline int read(){
char ch=getchar(); int f=,x=;
while(ch<''||ch>''){if(ch=='-')f=-; ch=getchar();}
while(ch>=''&&ch<='')x=x*+ch-'',ch=getchar();
return f*x;
}
multiset<int,greater<int> >st1;
multiset<int>st2;
int n,m,k,now,ans; struct nd{int t,w,n;}nds[][maxn*]; int ess[],g[][maxn];
int main(){
n=read(); m=read(); k=read();
inc(i,,n){
int x=read(),y=read(),z=read();
if(x<y)nds[][++ess[]]=(nd){y,z,g[][x]},g[][x]=ess[];
else nds[][++ess[]]=(nd){y,z,g[][x]},g[][x]=ess[];
}
now=;
inc(i,,m){
if(st1.find(i)!=st1.end()){int x=st1.erase(i); ans+=x; now-=x;}
for(int j=g[][i];j;j=nds[][j].n){
while(now<k&&nds[][j].w)st1.insert(nds[][j].t),nds[][j].w--,now++;
if(now==k){
while(*st1.begin()>nds[][j].t&&nds[][j].w)
st1.erase(st1.begin()),st1.insert(nds[][j].t),nds[][j].w--;
}
}
}
now=;
for(int i=m;i>=;i--){
if(st2.find(i)!=st2.end()){int x=st2.erase(i); ans+=x; now-=x;}
for(int j=g[][i];j;j=nds[][j].n){
while(now<k&&nds[][j].w)st2.insert(nds[][j].t),nds[][j].w--,now++;
if(now==k){
while(*st2.begin()<nds[][j].t&&nds[][j].w)
st2.erase(st2.begin()),st2.insert(nds[][j].t),nds[][j].w--;
}
}
}
printf("%d",ans); return ;
}
20161115
最新文章
- VBScript使用CDO.Message发送邮件
- AX7: How to deploy a Package
- Scalaz(32)- Free :lift - Monad生产线
- sql联合查询
- 【vijos1900】 学姐吃寿司
- One Edit Distance
- Android-调用优酷SDK上传视频
- ORACLE 常用字符函数
- hdu 1573 x问题(中国剩余定理)HDU 2007-1 Programming Contest
- 划分分区GPT11
- ZOJ2317-Nice Patterns Strike Back:矩阵快速幂,高精度
- encodeURI与encodeURIComponent的区别
- 简单实用的下拉菜单(CSS+jquery)
- 关于多线程的一个例子(UI实时显示)
- notepad 是doc 调出记事本文件
- 宠物收养场 Treap
- JavaWeb程序连接SQLserver数据库
- HTTPS与MITM
- c#之依赖注入
- jquery项目中一些常用方法