Codeforces Round #353 (Div. 2) C. Money Transfers (思维题)

题目链接:http://codeforces.com/contest/675/problem/C

给你n个bank,1~n形成一个环,每个bank有一个值,但是保证所有值的和为0。有一个操作是每个相邻的bank之间可以转钱,让你用最少的操作使每个bank的值为0。

一开始没什么思路,看了一下别人的题解,果然还是还是native...

要是让操作次数变少,首先划分和为0的区间个数要尽量多,比如一个区间的长度为k,那么他操作次数为k - 1,所以总的操作次数就是(n - 区间的个数)。

那么要算出区间的个数的话,那就要先算前缀和,比如前缀和sum[r] = x ,sum[l] = x其中(r > l),那么(l , r]之间的和为0。所以我们从1到n遍历一下前缀和,计算其中前缀和相同且次数出现最多的个数就行了。

 #include <bits/stdc++.h>
using namespace std;
typedef __int64 LL;
map <LL , int> mp;
int main()
{
int n , res = ;
LL sum = , num;
scanf("%d" , &n);
for(int i = ; i < n ; ++i) {
scanf("%I64d" , &num);
sum += num;
mp[sum]++;
res = max(res , mp[sum]);
}
printf("%d\n" , n - res);
}
上一篇:table 表格 细边框 最简单样式


下一篇:BRCM5.02编译四: ERROR: lzo/lzo1x.h development library is required for build