用c++语言的代码完成以下题目:蒜头君要进行小屋装修改造,现在他有 n 块木料,第 i 块木料的高度为 2^{ai} 。蒜头君可以对木料进行若干次操作,直到无法操作为止: 选择两块相邻且高度相同的木料,将两块木料钉到一起,形成一块儿更高的木料,高度为两块木料的高度之和。 现在蒜头君想要知道:他最少可能进行多少次操作。
时间: 2023-05-25 15:07:01 浏览: 62
c++类的一个练习
思路:由于两块高度相同的木料才可以进行操作,所以我们要找到所有相同高度的木料并进行聚合,直到最终只剩下一块木料为止。因此,我们可以使用一个 map 来记录每种高度的木料的数量,然后从小到大不断找相邻两个高度相同的木料进行聚合,直到只剩下一块木料为止。
代码实现:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <stdbool.h>
#include <string.h>
#define MAXN 100000
int n, a[MAXN + 5];
int cnt[MAXN * 2 + 5];
int main() {
scanf("%d", &n);
for (int i = 1;i <= n;i++) {
scanf("%d", &a[i]);
cnt[a[i]]++;
}
int ans = 0;
bool flag = true;
while (flag) {
flag = false;
for (int i = 0;i <= 20;i++) {
if (cnt[i] >= 2) {
int t = cnt[i] / 2;
cnt[i + 1] += t;
cnt[i] -= t * 2;
ans += t;
flag = true;
}
}
}
printf("%d\n", ans);
return 0;
}
阅读全文