网站开发定制合同范本,汉中建设工程招标信息网,免费设计logo的手机软件,仪器仪表公司网站模版GYM 101669F - Binary Transformations 做法#xff1a;如果不存在一个位置p \((a[p]1,b[p]1)\)#xff0c;那么答案就是贪心的先把所有的1#xff0c;按价值从大到小变为0,所有的0,按价值从小到大变为1。如果存在一些位置p#xff0c;我们就枚举一开始把多少p转成0,显然价… GYM 101669F - Binary Transformations 做法如果不存在一个位置p \((a[p]1,b[p]1)\)那么答案就是贪心的先把所有的1按价值从大到小变为0,所有的0,按价值从小到大变为1。如果存在一些位置p我们就枚举一开始把多少p转成0,显然价值越大的p越优。现在考虑如何模拟我们可以用2个set一个维护一开始要从0变1的数另一个维护最后要由1变0的数插入\(O(log n)\)遍历\(O(n)\)总的复杂度\(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;}
vectorll v3;
multisetll tmp1,tmp2;
ll cal(int x) {ll ans 0, ss sum;if(x) tmp1.insert(v3[x-1]),tmp2.insert(v3[x-1]);multisetll::iterator it1;multisetll::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,a1);scanf( %s,b1);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) sumc[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;
}转载于:https://www.cnblogs.com/RRRR-wys/p/9720412.html
