首页 > 代码库 > BZOJ2620 [Usaco2012 Mar]Haybale Restacking
BZOJ2620 [Usaco2012 Mar]Haybale Restacking
恩，非常好的题。。。至少思路非常巧妙
首先可以得到性质：对于相邻的两堆A & B，A给B然后B再给A是完全没有意义的。。。也就是说只能单向传递
然后我们记下每个点要给（被给）多少堆干草a[i]
同时可以计算出del[i]，表示若第i堆只向右传且第n堆不向第1堆运任何干草的情况下i - 1向i传递干草的数量
del[i] = del[i - 1] + a[i - 1]（其实就是前缀和）
现在1可以向右移了，设向右移x堆，则ans = Σabs(del[i] - x)
故x = mid(del + 1, del + n + 1)时，ans最小
更加详细见lrj白书P4。。。
1 /************************************************************** 2 Problem: 2620 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:68 ms 7 Memory:1588 kb 8 ****************************************************************/ 9 10 #include <cstdio>11 #include <algorithm>12 13 using namespace std;14 typedef long long ll;15 const int N = 100005;16 int n;17 int a[N], del[N];18 ll ans;19 20 inline int read(){21 int x = 0, sgn = 1;22 char ch = getchar();23 while (ch < ‘0‘ || ch > ‘9‘){24 if (ch == ‘-‘) sgn = -1;25 ch = getchar();26 }27 while (ch >= ‘0‘ && ch <= ‘9‘){28 x = x * 10 + ch - ‘0‘;29 ch = getchar();30 }31 return sgn * x;32 }33 34 35 int main(){36 n = read();37 int i, m = (n + 1) >> 1;38 for (i = 1; i <= n; ++i)39 a[i] = read(), a[i] -= read();40 for (i = 2; i <= n; ++i)41 del[i] = a[i - 1] + del[i - 1];42 del[1] = a[n] + del[n];43 sort(del + 1, del + n + 1);44 for (i = 1; i <= n; ++i)45 ans += abs(del[m] - del[i]);46 printf("%lld\n", ans);47 return 0;48 }
BZOJ2620 [Usaco2012 Mar]Haybale Restacking
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。