直线上有n个等距的村庄，，每个村庄要么买酒，要么卖酒。把k个单位的酒从一个村庄运到相邻村庄需要k个单位的劳动力。问最少需要多少劳动力才能满足所有村庄的需求
思路贪心
#include<cstdio> #include<cstring> #include<cmath> #include<cstdlib> #include<iostream> #include<algorithm> #include<vector> #include<map> #include<queue> #include<stack> #include<string>#include<map> #include<set>#define eps 1e-6 #define LL long long using namespace std; const int maxn = 100000 + 100;const int INF = 0x3f3f3f3f;//freopen("input.txt", "r", stdin);int C[maxn], n;int lowbit(int x) { return x&(-x);}int sum(int x) {if(x == 0) return 0;int ret = 0;while(x > 0) {ret += C[x]; x -= lowbit(x);}return ret;}void add(int x, int d) {while(x <= n) {C[x] += d; x += lowbit(x);}}LL solve(int left, int right) {if(left == right) return (LL)0;if(left+1 == right) return (LL)abs(sum(right)-sum(left));int mid = (left + right) >> 1;int tmp = sum(mid) – sum(left-1);add(mid, -tmp); add(mid+1, tmp);return solve(left, mid) + solve(mid+1, right) + (LL)abs(tmp); }void init() {memset(C, 0, sizeof(C));int tmp;for(int i = 1; i <= n; i++) {cin >> tmp;add(i, tmp); }}int main() {//freopen("input.txt", "r", stdin);while(scanf("%d", &n) == 1 && n) {init();cout << solve(1, n) << endl;}return 0;}
勇于接受自己的不完美，认清自己不足的地方，
