uva 11054 Gerovia的酒交易（贪心+树状数组）

2019-04-14 08:36发布

站内文章 / 模拟电子
14045 0 1383
直线上有n个等距的村庄，每个村庄要么买酒，要么卖酒。把k个单位的酒从一个村庄运到相邻村庄需要k个单位的劳动力。问最少需要多少劳动力才能满足所有村庄的需求 思路贪心 #include #include #include #include #include #include #include #include #include #include #include #include #include #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; }

热门文章