首页 > 代码库 > [HDOJ5933]ArcSoft's Office Rearrangement（贪心）

[HDOJ5933]ArcSoft's Office Rearrangement（贪心）

2024-08-18 07:55:00   219人阅读

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5933

题意：长度为nn的数组: a_1, a_2, \cdotsa?1??,a?2??,?, 每次操作要么可以merge两个相邻的数为一个, 值为两个数的和; 要么可以把一个数分裂成两个, 两个数的和为原数. 用最少的操作把数组变换成长度为KK且所有数值相等的数组, 无解输出-1?1。

读错题了啊…以为是任意merge，题意是相邻的merge。

 

分情况讨论，每次判断当前点是比avg大还是小，如果大的话就把多余的部分放到下一个点上，拆操作是商-1次。余数merge到下一个的操作是2次（一次拆，一次merge），如果小于平均的话就全merge到上一个去。 当然考虑当前和下一个的和能不能作为一次。

 

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 typedef long long LL;
 5 const int maxn = 100100;
 6 int n, k;
 7 LL a[maxn];
 8 LL avg;
 9 
10 int main() {
11     // freopen("in", "r", stdin);
12     int T, _ = 1;
13     scanf("%d", &T);
14     while(T--) {
15         scanf("%d%d",&n,&k);
16         printf("Case #%d: ", _++);
17         avg = 0;
18         LL s = 0;
19         for(int i = 1; i <= n; i++) {
20             scanf("%d", &a[i]);
21             s += a[i];
22         }
23         if(s % k != 0) {
24             puts("-1");
25             continue;
26         }
27         avg = s / k;
28         LL ret = 0;
29         for(int i = 1; i <= n; i++) {
30             if(a[i] < avg) {
31                 if(a[i] + a[i+1] <= avg) {
32                     ret++;
33                     a[i+1] = a[i] + a[i+1];
34                 }
35                 else {
36                     a[i+1] = a[i+1] - avg + a[i];
37                     ret += 2;
38                 }
39             }
40             else if(a[i] > avg) {
41                 LL p = a[i] / avg;
42                 LL q = a[i] % avg;
43                 if(q != 0) {
44                     a[i+1] += q;
45                     ret += 2;
46                 }
47                 ret += p - 1;
48             }
49         }
50         printf("%I64d\n", ret);
51     }
52     return 0;
53 }

 

[HDOJ5933]ArcSoft's Office Rearrangement（贪心）


联系
我们