牛客一 G-Game of Swapping Numbers

給出n個(gè)數(shù)ai和n個(gè)數(shù)bi，每一次可以交換兩個(gè)數(shù)ai和aj，最后求出$max{\sum }_{i=1}^n|a_i?b_i|$
數(shù)據(jù)范圍：2 <= n <= 5e5, -1e8 <= a, b <= 1e8, 0 <= k <= 1e8

貪心，先處理出來(lái)初始狀態(tài)的ans的值，然后每次交換要最大化自己的答案。我們考慮應(yīng)該如何去使答案增大。

對(duì)于$(a_i,b_i)$與$(a_j,b_j)$，假設(shè)都有a<=b,那么類似$a_i<=a_j<=b_i<=b_j$這樣，兩個(gè)區(qū)間沒(méi)有重疊的部分，這樣便無(wú)法用交換的方法將答案變大。而$a_i<=b_i<=a_j<=b_j$兩個(gè)區(qū)間不重疊的，可以交換來(lái)達(dá)到重疊的效果，這樣對(duì)于答案的增大的值為$(a_j?b_i)?2$。

由于a和b都是對(duì)應(yīng)的一組，所以交換a還是交換b對(duì)于答案影響是一樣的。每一次我們找出一組ab當(dāng)中更小的那個(gè)，放入大根堆，再將更大的那個(gè)放入小根堆。每次從大根堆當(dāng)中取出堆頂元素與小根堆的堆頂元素比較，如果更大的話邊可以更新答案，否則結(jié)束，這樣最多n次便可求出答案，用不到k的上限。

#include <bits/stdc++.h> using namespace std;const int N = 5e5 + 10; int a[N], b[N];priority_queue <int> mx, mn;int main() {//freopen("in.txt", "r", stdin);ios::sync_with_stdio(false);cin.tie(0);int T = 1;//cin >> T;while (T --){int n, k;cin >> n >> k;for (int i = 1; i <= n; i ++)cin >> a[i];for (int i = 1; i <= n; i ++)cin >> b[i];long long ans = 0;for (int i = 1; i <= n; i ++){ans += abs(a[i] - b[i]);if (a[i] >b[i]){mn.push(-a[i]);mx.push(b[i]);}else{mn.push(-b[i]);mx.push(a[i]);}}for (int i = 1; i <= k; i ++){int x = mn.top(), y = mx.top();mn.pop(); mx.pop();if (x + y <= 0) break;ans += ((x + y) << 1);}cout << ans;}return 0; }

總結(jié)

以上是生活随笔為你收集整理的牛客一 G-Game of Swapping Numbers的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。