首页 > 代码库 > bzoj1745: [Usaco2005 oct]Flying Right 飞行航班（贪心+map）
bzoj1745: [Usaco2005 oct]Flying Right 飞行航班（贪心+map）
之前做过一道基本一样的题目，抽象出来就是有个容量为c的载体，一些线段上某个点到另一个点要运输w个东西，求从头到尾最多能运多少东西。
这种模型可以用贪心做，用map，map[r]表示r的那个点，我们准备运多少头牛到那里，但是还没运到。
用map的好处是不管是插入还是删除，它都按坐标从小到大排。
那么先把所有的边按左端点从小到大排，对于当前边，
容量未满的时候，直接加入map
容量满的时候，若map中最大的坐标比这条边的右端点要大，那么显然用当前边替换会更好。
运到的怎么处理呢？
当我们枚举到这个点，这个点的map值大于零说明有牛运到这里了，则ans+=map[now],cap-=map[now]，并从map中删除这个点。
还有这道题从1到n还要从n到1回来，可以做两遍，也可以把回去的那段倒着拼在后面
map的用法还不是很熟练，写了一个多小时才写完，不过一次AC也是非常爽的= =
1 #include<stdio.h> 2 #include<string.h> 3 #include<algorithm> 4 #include<map> 5 #define INF 1000000000 6 using namespace std; 7 const int maxn = 20010; 8 struct node{ 9 int l,r,w;10 }e[maxn*5];11 map<int,int> mp;12 int n,m,c,cap,head,ans;13 14 bool cmp(node a, node b){15 if (a.l==b.l) return a.r<b.r;16 else return a.l<b.l;17 }18 19 int main(){20 scanf("%d%d%d", &m, &n, &c);21 for (int i=1; i<=m; i++){22 scanf("%d%d%d", &e[i].l, &e[i].r, &e[i].w);23 if (e[i].l>e[i].r) e[i].l=2*n-e[i].l,e[i].r=2*n-e[i].r;24 }25 sort(e+1,e+1+m,cmp);26 mp.clear();27 mp[-INF]=0; cap=0;28 map<int,int>::iterator it;29 head=1; ans=0;30 for (int now=1; now<=2*n-1; now++){31 if (mp[now]>0){32 ans+=mp[now];33 cap-=mp[now];34 it=mp.find(now);35 mp.erase(it);36 }37 while (e[head].l<now) head++;38 while (e[head].l==now){39 int to=e[head].r,num=e[head].w;40 while (cap<c && num>0) cap++,num--,mp[to]++;41 if (cap==c && num)42 for (it=--mp.end(); it!=mp.begin();){43 if ((it->first)>to){44 if ((it->second)>num){45 (it->second)-=num;46 mp[to]+=num;47 break;48 }else{49 mp[to]+=(it->second);50 num-=(it->second);51 mp.erase(it--);52 }53 }else break;54 }55 head++;56 }57 }58 printf("%d\n", ans);59 return 0;60 }
bzoj1745: [Usaco2005 oct]Flying Right 飞行航班（贪心+map）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。