取尺法 Codeforces675C Money Transfers

取尺法 Codeforces675C Money Transfers

传送门：点击打开链接

题意：有n家银行围成一个圈，有个人在有些银行里欠了钱，在一些银行里有存钱，欠的钱总数等于存的钱总数。

现在可以有操作，如果两个银行相邻，那么就能在一个银行转任意多的钱到另一个银行。问最少的操作次数，使得在所有银行的存款钱数都为0

思路：这道题的脑洞非常大。。

首先我们要发现第一个贪心。如果有一段子串，里面的数字之和等于0，那么在这段子串中移动数字，所需要的代价为子串长度len-1

那么问题就转换成了，我们在这个圈中能找到多少段子串，里面的数字之和等于0，而且段数越多越好，记为k

那么很明显，答案就是n-k

现在问题来了，如何来求满足题意的最大的k

首先，我们考虑用前缀和来存放，如果遇到两个位置，前缀和相等，那么中间那一段数字之和肯定等于0。

接下来就是一个跳跃性的思考了，那么如果某个前缀和的值出现了k次，是不是就是我们上述的k呢？

答案是正确的！假如有k个位置的前缀和相等，那么中间k-1段子串内数字之和一定都是0，由于总数是0，那么最前面和最后面连着的那一段也肯定是0

所以，我们记录所有的前缀和的值，然后排序。然后用取尺法记录一个数出现的最多次数，就做完了

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <bitset>
#include <string>
#include <vector>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
#define fuck(x) cout<<"["<<x<<"]";
#define FIN freopen(&#","r",stdin);
#define FOUT freopen(&#","w+",stdout);
//#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;const int MX = 1e5 + 5;LL A[MX];
int main() {int n; //FIN;scanf("%d", &n);for(int i = 1; i <= n; i++) {scanf("%I64d", &A[i]);A[i] += A[i - 1];}sort(A + 1, A + 1 + n);int i, j, ans = 0;for(i = 1; i <= n; i = j + 1) {for(j = i; j < n && A[j + 1] == A[i]; j++);ans = max(ans, j - i + 1);}printf("%dn", n - ans);return 0;
}