GYM 101669F - Binary Transformations

---

做法：如果不存在一個(gè)位置p \((a[p]=1,b[p]=1)\)，那么答案就是貪心的先把所有的1，按價(jià)值從大到小變?yōu)?,所有的0,按價(jià)值從小到大變?yōu)?。如果存在一些位置p，我們就枚舉一開始把多少p轉(zhuǎn)成0,顯然價(jià)值越大的p越優(yōu)?，F(xiàn)在考慮如何模擬，我們可以用2個(gè)set，一個(gè)維護(hù)一開始要從0變1的數(shù)，另一個(gè)維護(hù)最后要由1變0的數(shù)，插入\(O(log n)\)，遍歷\(O(n)\)，總的復(fù)雜度\(O(n^2)\)

#include <bits/stdc++.h> #define pb push_back typedef long long ll; const int N = 5010; using namespace std; int n; ll c[N], ans, sum; char a[N], b[N]; bool cmp(ll a,ll b) {return a > b;} vector<ll> v3; multiset<ll> tmp1,tmp2; ll cal(int x) {ll ans = 0, ss = sum;if(x) tmp1.insert(v3[x-1]),tmp2.insert(v3[x-1]);multiset<ll>::iterator it1;multiset<ll>::reverse_iterator it2;for(it2 = tmp1.rbegin(); it2 != tmp1.rend(); ++it2) {ss -= (*it2); ans += ss;}for(it1 = tmp2.begin(); it1 != tmp2.end(); ++it1) {ss += (*it1); ans += ss;}return ans; } int main() {scanf("%d",&n);for(int i = 1; i <= n; ++i) scanf("%lld",&c[i]);scanf(" %s",a+1);scanf(" %s",b+1);for(int i = 1; i <= n; ++i) {if(a[i] != b[i]) {if(a[i] == '1' && b[i] == '0') tmp1.insert(c[i]);else tmp2.insert(c[i]);}else if(a[i] == '1' && b[i] == '1') v3.pb(c[i]);if(a[i] == '1') sum+=c[i];}sort(v3.begin(),v3.end(),cmp);ans = (ll)(1e18);int v3n = v3.size();for(int i = 0; i <= v3n; ++i) ans = min(ans,cal(i));printf("%lld\n",ans);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/RRRR-wys/p/9720412.html

總結(jié)

以上是生活随笔為你收集整理的GYM 101669F - Binary Transformations的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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