首页 > 代码库 > Codeforces-808D Array Division (multiset 折半？？？)

Codeforces-808D Array Division (multiset 折半？？？)

2024-11-04 19:40:39   204人阅读

题目链接：

http://codeforces.com/problemset/problem/808/D

题意:

给定一个数列，移动0或1个数字，使数列能从某个位置分开前后两半的和相等。

思路：

from: http://www.cnblogs.com/robin1998/p/6864278.html

我们可以假想有个隔板从左向右扫，每次两边的和的差值为x，若能找到某一边（看那边大）的一个数为x/2，则将它放到另一边就满足条件。扫一遍O（n），数据是无序的，如果暴力查找则总复杂度O(n^2)无法承受，我们可以维护两个平衡树做到O(nlogn)，这里我们发现完全可以用STL的multiset代替。

菜鸡觉得是很奇妙的想法，这也是折半查找的思想把？

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MS(a) memset(a,0,sizeof(a))
#define MP make_pair
#define PB push_back
const int INF = 0x3f3f3f3f;
const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}
    while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}
    return x*f;
}
//////////////////////////////////////////////////////////////////////////
const int maxn = 1e5+10;

int n,a[maxn];
multiset<ll> s1,s2;
multiset<ll>::iterator it;

int main(){
    cin >> n;
    ll sum = 0;
    for(int i=1; i<=n; i++){
        cin >> a[i];
        sum += a[i];
        s2.insert(a[i]);
    }
    if(sum%2) return 0*puts("NO");
    ll sum1=0,sum2=sum;
    bool f = 0;
    for(int i=1; i<=n; i++){
        if(sum1 == sum2) { f=1; break;}
        ll t = abs(sum1-sum2);
        if(sum1 > sum2){
            if(t%2==0 && s1.count(t/2)){
                f = 1;
                break;
            }
        }else{
            if(t%2==0 && s2.count(t/2)){
                f = 1;
                break;
            }
        }
        sum1 += a[i]; sum2 -= a[i];
        s1.insert(a[i]);
        it = s2.find(a[i]); s2.erase(it);
    }
    if(f) puts("YES");
    else puts("NO");

    return 0;
}

 

Codeforces-808D Array Division (multiset 折半？？？)


联系
我们