首页 > 代码库 > Educational Codeforces Round 21 D. Array Division

Educational Codeforces Round 21 D. Array Division

2024-09-25 16:56:39   217人阅读

题目链接：Educational Codeforces Round 21 D. Array Division

题意：

给你n个数，现在你可以改变1<=个数的位置，然后问你是否存在有一个k，使得sum(a[i])(1<=i<=k)==sum(a[j])(k+1<=j<=n)

题解：

 分析：

如果需要将一个数移动，无非就是将这个数从第一部分移到第二部分，或者从第二部分移到第一部分。

所以，我们只需要开两个map来记录一下两部分有哪些数。

当两部分的差值/2等于其中一部分的一个数时，那么就可以YES了。

技术分享 
 1 #include<bits/stdc++.h>
 2 #define F(i,a,b) for(int i=a;i<=b;i++)
 3 using namespace std;
 4 typedef long long ll;
 5 
 6 const int N=1e5+7;
 7 ll a[N];
 8 map<ll,int>mp;
 9 map<ll,int>mp2;
10 int main()
11 {
12     int n;ll sum1=0,sum2=0;
13     scanf("%d",&n);
14     F(i,1,n)scanf("%lld",a+i),sum2+=a[i],mp[a[i]]++;
15     if(sum2&1){puts("NO");return 0;}
16     ll aim=sum2/2;
17     F(i,1,n)
18     {
19         ll tp=sum2-aim;
20         if(tp>0&&mp[tp]>0){puts("YES");return 0;}
21         if(tp<0&&mp2[-tp]>0){puts("YES");return 0;}
22         sum2-=a[i];
23         mp[a[i]]--;
24         mp2[a[i]]++;
25     }
26     puts("NO");
27     return 0;
28 }
View Code

 

Educational Codeforces Round 21 D. Array Division


联系
我们