首页 > 代码库 > 【贪心+Treap】BZOJ1691-[Usaco2007 Dec]挑剔的美食家
【贪心+Treap】BZOJ1691-[Usaco2007 Dec]挑剔的美食家
【题目大意】
有n头奶牛m种牧草，每种牧草有它的价格和鲜嫩度。每头奶牛要求它的牧草的鲜嫩度要不低于一个值，价格也不低于一个值。每种牧草只会被一头牛选择。问最少要多少钱？
【思路】
显然的贪心，把奶牛和牧草都按照鲜嫩度由大到小排序，对于每奶牛把鲜嫩度大于它的都扔进treap，然后找出后继。
不过注意后继的概念是大于它且最小的，然而我们这里是可以等于的，所以应该是找cow[i].fresh-1的后继，注意一下……
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 using namespace std; 7 typedef long long ll; 8 const int MAXN=100000+50; 9 const int INF=0x7fffffff; 10 struct node 11 { 12 int fresh,price; 13 bool operator < (const node &x) const 14 { 15 return (fresh>x.fresh);//注意是由大到小排序 16 } 17 }cow[MAXN],grass[MAXN]; 18 struct treap 19 { 20 int key,cnt,priority; 21 treap* lson; 22 treap* rson; 23 treap() 24 { 25 cnt=1; 26 priority=rand(); 27 lson=rson=NULL; 28 } 29 }; 30 treap* root=NULL; 31 int n,m; 32 33 void RightRotate(treap* &rt) 34 { 35 treap* tmp=rt->lson; 36 rt->lson=tmp->rson; 37 tmp->rson=rt; 38 rt=tmp; 39 } 40 41 void LeftRotate(treap* &rt) 42 { 43 treap* tmp=rt->rson; 44 rt->rson=tmp->lson; 45 tmp->lson=rt; 46 rt=tmp; 47 } 48 49 void insert(treap* &rt,int x) 50 { 51 if (rt==NULL) 52 { 53 rt=new treap;//不要忘记了新建 54 rt->key=x; 55 } 56 else if (rt->key==x) rt->cnt++; 57 else 58 { 59 if (rt->key>x) 60 { 61 insert(rt->lson,x); 62 if (rt->lson->priority>rt->priority) RightRotate(rt); 63 } 64 if (rt->key<x) 65 { 66 insert(rt->rson,x); 67 if (rt->rson->priority>rt->priority) LeftRotate(rt); 68 } 69 } 70 } 71 72 void del(treap* &rt,int x) 73 { 74 if (rt->key==x) 75 { 76 if (rt->cnt>1) rt->cnt--; 77 else 78 { 79 treap* tmp=rt; 80 if (rt->lson==NULL) 81 { 82 rt=rt->rson; 83 delete tmp; 84 } 85 else if (rt->rson==NULL) 86 { 87 rt=rt->lson; 88 delete tmp; 89 } 90 else 91 { 92 if (rt->lson->priority>rt->rson->priority) RightRotate(rt),del(rt->rson,x); 93 else LeftRotate(rt),del(rt->lson,x); 94 } 95 } 96 } 97 else 98 { 99 if (x<rt->key) del(rt->lson,x);100 else del(rt->rson,x);101 }102 }103 104 int suc(treap* &rt,int x)105 {106 int ans=INF;107 treap* tmp=rt;108 while (tmp)109 {110 if (tmp->key>x)111 {112 ans=min(ans,tmp->key);113 tmp=tmp->lson;114 }115 else tmp=tmp->rson;116 }117 return ans;118 }119 120 void init()121 {122 scanf("%d%d",&n,&m);123 for (int i=1;i<=n;i++) scanf("%d%d",&cow[i].price,&cow[i].fresh);124 for (int i=1;i<=m;i++) scanf("%d%d",&grass[i].price,&grass[i].fresh);125 sort(cow+1,cow+n+1);126 sort(grass+1,grass+m+1);127 }128 129 ll solve()130 {131 int j=1;132 ll ans=0;133 for (int i=1;i<=n;i++)134 {135 while (grass[j].fresh>=cow[i].fresh && j<=m)136 {137 insert(root,grass[j].price);//这里一开始把j打成i了 138 j++;139 }140 int find=suc(root,cow[i].price-1);//注意由于这里是不低于，也就是≥，并不是取cow[i].price的后继，而是cow[i].price-1的 141 if (find==INF) return(-1);142 else143 {144 ans+=(ll)find;145 del(root,find);146 }147 }148 return ans;149 }150 151 int main()152 {153 init();154 printf("%lld",solve());155 return 0;156 }
【贪心+Treap】BZOJ1691-[Usaco2007 Dec]挑剔的美食家
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。