https://ac.nowcoder.com/acm/contest/358/E
题意:
出题人有两个数组, A,B, 请你把两个数组归并起来使得 cost=∑ici 最小, 归并要求原数组的数的顺序在新数组中不改变.
题解:
先分别处理 A 和 B 数组, 把 A 先分成 n 段, 把某段均值大于前面的一段, 就把这两段合并. 处理完 A,B 段后就可以取大原则归并.
- #include <algorithm>
- #include <iterator>
- #include <iostream>
- #include <cstring>
- #include <cstdlib>
- #include <iomanip>
- #include <bitset>
- #include <cctype>
- #include <cstdio>
- #include <string>
- #include <vector>
- #include <stack>
- #include <cmath>
- #include <queue>
- #include <list>
- #include <map>
- #include <set>
- #include <cassert>
- using namespace std;
- #define lson (l , mid , rt <<1)
- #define rson (mid + 1 , r , rt << 1 | 1)
- #define debug(x) cerr << #x << "=" << x << "\n";
- #define pb push_back
- #define pq priority_queue
- typedef long long ll;
- typedef unsigned long long ull;
- //typedef __int128 bll;
- typedef pair<ll ,ll> pll;
- typedef pair<int ,int> pii;
- typedef pair<int,pii> p3;
- //priority_queue<int> q;// 这是一个大根堆 q
- //priority_queue<int,vector<int>,greater<int>>q;// 这是一个小根堆 q
- #define fi first
- #define se second
- //#define endl '\n'
- #define OKC iOS::sync_with_stdio(false);cin.tie(0)
- #define FT(A,B,C) for(int A=B;A <= C;++A) // 用来压行
- #define REP(i , j , k) for(int i = j ; i <k ; ++i)
- #define max3(a,b,c) max(max(a,b), c);
- #define min3(a,b,c) min(min(a,b), c);
- //priority_queue<int ,vector<int>, greater<int>>que;
- const ll mos = 0x7FFFFFFF; //2147483647
- const ll nmos = 0x80000000; //-2147483648
- const int inf = 0x3f3f3f3f;
- const ll inff = 0x3f3f3f3f3f3f3f3f; //18
- const int mod = 1e8+7;
- const double esp = 1e-8;
- const double PI=acos(-1.0);
- const double PHI=0.61803399; // 黄金分割点
- const double tPHI=0.38196601;
- template<typename T>
- inline T read(T&x){
- x=0;int f=0;char ch=getchar();
- while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
- while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
- return x=f?-x:x;
- }
- /*-----------------------showtime----------------------*/
- const int maxn = 1e5+9;
- int A[maxn],B[maxn];
- struct node{
- ll sum;int cnt;
- friend bool operator <(node a, node b){
- return a.sum * b.cnt < b.sum * a.cnt;
- }
- friend node operator + (node a,node b){
- return (node) {a.sum + b.sum, a.cnt + b.cnt};
- }
- }S[maxn],T[maxn];
- int C[maxn*2];
- void add(int op, int l,int r,int &now){
- for(int i=l; i<=r; i++){
- if(op==1) C[now++] = A[i];
- else C[now++] = B[i];
- }
- }
- int main(){
- int n,m; scanf("%d%d", &n, &m);
- for(int i=1; i<=n; i++) {
- scanf("%d", &A[i]);
- }
- for(int i=1; i<=m; i++){
- scanf("%d", &B[i]);
- }
- int tot1 = 0;
- for(int i=1; i<=n; i++){
- S[++tot1] = (node) {A[i], 1};
- while(tot1>1 && S[tot1-1] <S[tot1]){
- S[tot1-1] = S[tot1-1] + S[tot1];
- tot1--;
- }
- }
- int tot2 = 0;
- for(int i=1; i<=m; i++){
- T[++tot2] = (node) {B[i], 1};
- while(tot2> 1&& T[tot2-1] < T[tot2]){
- T[tot2-1] = T[tot2-1] + T[tot2];
- tot2--;
- }
- }
- S[++tot1] = (node){-1, 1};
- T[++tot2] = (node){-1, 1};
- int L=1,R=1;
- int prel=1,prer=1,now=1;
- while(L < tot1 || R < tot2){
- if(S[L] < T[R]){
- add(2, prer,prer+T[R].cnt-1,now);
- prer += T[R].cnt;
- R++;
- }
- else {
- add(1, prel,prel+S[L].cnt-1,now);
- prel += S[L].cnt;
- L++;
- }
- }
- ll ans = 0;
- for(int i=1; i<=n+m;i++){
- ans += 1ll*i*C[i];
- // cout<<C[i]<<" ";
- }
- // cout<<endl;
- printf("%lld\n", ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2927449.html