电源

codeforces 732E （贪心)

2019-07-13 22:25发布

站内文章 / 电源技术
11408 0 1463

题目链接：点击这里

题意：给出n个电脑，m个电源，电脑有一个值ai,电源有一个值bi，电脑和电源能够配对当且仅当ai=bi。有无穷多个适配器，每对电源用一个适配器bi就减少一半（向上取整）。一个电源可以用很多次适配器。求最多配对多少电脑和电源，以及在最多配对下用的最少的适配器。还要输出方案。 将电源按照从小到大依次尝试和电脑配对，如果能够配对成功就配对。可以反证，假设按照这个顺序配对会使得配对数减少，也就是说有一个比他大的电源本应该和这个电脑相配。因为这两个电源都匹配到了这个电脑，所以当前枚举的电源往下能够匹配的电脑也能被那个比他大的电源匹配掉。
那么这样贪心会不会使得适配器数量不是最佳呢？容易证明是最少的。因为如果这个电源配对了一个电脑而了占据上面某一个比他大的电源，如果本来就本来就只能配对这一个电脑，显然用较小的电源是最优的。否则任意配对方案的适配器花费是一样的。
输出方案比较搞，用map这种东西瞎搞就好了。 #include #include #include #include #include #include #include #include using namespace std; #define maxn 200005 int a[maxn], b[maxn], c[maxn]; map <int, int> gg; struct node { int num, id; bool operator < (const node &a) const { return num < a.num || (num == a.num && id < a.id); } }s[maxn], p[maxn], fuck[maxn]; int n, m; int main () { //freopen ("in.txt", "r", stdin); ios::sync_with_stdio (0); cin >> n >> m; gg.clear (); for (int i = 1; i <= n; i++) { cin >> p[i].num; p[i].id = i; gg[p[i].num] += 1; } for (int i = 1; i <= m; i++) { cin >> s[i].num; s[i].id = i; } sort (s+1, s+1+m); int num = 0; long long tot = 0;//配对成功 总的适配器 memset (b, 0, sizeof b); for (int i = 1; i <= m; i++) { int tmp = 0; while (1) { if (gg[s[i].num] >= 1) { gg[s[i].num]--; fuck[num++] = s[i]; tot += tmp; b[s[i].id] = tmp;//和i号电源相配用b[i]个适配器 break; } else { if (s[i].num == 1) break; s[i].num = (s[i].num+1)/2; tmp++; } } } cout << num << " " << tot << endl; memset (a, 0, sizeof a); sort (fuck, fuck+num); for (int i = 1; i <= n; i++) { int pos = lower_bound (fuck, fuck+num, (node){p[i].num, -1})-fuck; if (pos == num) continue; if (fuck[pos].num == p[i].num) { a[i] = fuck[pos].id; fuck[pos].id = -2; } } for (int i = 1; i <= m; i++) cout << b[i] << (i == m ? ' ' : ' '); for (int i = 1; i <= n; i++) cout << a[i] << (i == n ? ' ' : ' '); return 0; }

热门文章