首页 > 代码库 > Codeforces 732e [贪心][stl乱搞]
Codeforces 732e [贪心][stl乱搞]
/* 不要低头,不要放弃,不要气馁,不要慌张 题意: 给n个插座,m个电脑。每个插座都有一个电压,每个电脑都有需求电压。 每个插座可以接若干变压器,每个变压器可以使得电压变为x/2上取整。 有无限个变压器供应。 问最多能使得多少个插座与电脑匹配,使得电压一致。 如果有多种方案,输出需要变压器总数最小的那种。 输出匹配数量 输出每个插座需要接多少个变压器。输出每台电脑匹配哪个插座。 思路: 贪心 乱搞 先从小到大将插座排序,然后从地第一个插座开始,不断除以2上取整。不断找是否可以匹配。找到匹配就停止。 记录个数即可。 这样可以保证所用变压器总数最少。 */ #include<bits/stdc++.h> #define N 200050 using namespace std; struct st{ st(){} st(int a,int b){ aa=a;id=b; } int aa,id; }; bool operator < (const st &a,const st &b){ return a.aa<b.aa; } bool cmp(st a,st b){ return a.aa<b.aa; } multiset<st>b; st a[N]; int ansa[N],ansb[N]; int main() { int n,m; st tmp; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ scanf("%d",&tmp.aa); tmp.id=i; b.insert(tmp); } for(int i=1;i<=m;i++){ scanf("%d",&a[i].aa); a[i].id=i; } sort(a+1,a+1+m,cmp); long long c=0; for(int i=1;i<=m;i++){ int num=0; bool ok=0; while(a[i].aa>1){ if(b.find(st(a[i].aa,0))!=b.end()){ ok=1; c+=num; tmp=*b.find(st(a[i].aa,0)); ansa[a[i].id]=num; ansb[tmp.id]=a[i].id; b.erase(b.find(st(a[i].aa,0))); break; } a[i].aa=(a[i].aa+1)/2; num++; } if(!ok){ if(b.find(st(a[i].aa,0))!=b.end()){ ok=1; c+=num; tmp=*b.find(st(a[i].aa,0)); ansa[a[i].id]=num; ansb[tmp.id]=a[i].id; b.erase(b.find(st(a[i].aa,0))); } } } int dd=b.size(); dd=n-b.size(); printf("%d %lld\n",dd,c); for(int i=1;i<=m;i++){ printf("%d ",ansa[i]); } puts(""); for(int i=1;i<=n;i++){ printf("%d ",ansb[i]); } }
Codeforces 732e [贪心][stl乱搞]
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。