[Codeforces] 675C. Money Transfers

題目連結:http://codeforces.com/problemset/problem/675/C

---

想了很久才知道方向錯了QAQ
作法是枚舉每個人往右邊推過去(可以證明只要枚舉所有人往右走就一定是好的)，那仔細觀察就會發現我們要省幾個就是看我們走過來有幾個前綴為零，而枚舉每一個人做開頭的時候其實我們就是問一直把最後的放到前面，也就是把前面加值，最後一個減值接著再查一下有幾個0就好了XD

#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
const int N = 100000 + 5;

map<lld,int> cnt;
lld arr[N];

int main(int argc, char* argv[]){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n; cin>>n;
	lld cur = 0;
	for(int i=0;i<n;i++){
		cin>>arr[i];
		cur += arr[i];
		cnt[cur]++;
	}
	int ans = n-cnt[0];
	cnt[0]--;
	for(int i=n-1;i>=0;i--){
		cur -= arr[i];
		ans = min(ans, n-cnt[cur]);
	}
	cout<<ans<<'\n';
	return 0;
}