使用c++代码模拟,每次选取模 1e9+7下最大的两个数 x 和 y,将 x 和 y 这两个数转变成 x×y−x−y。直到只剩下一个数,停止操作。 可以得知每次操作之后数的个数减少了一,一定能够变成一个数。
时间: 2023-04-10 13:05:18 浏览: 118
这是一个经典的算法问题,可以使用堆来实现。每次选取最大的两个数,可以使用一个大根堆来维护。将 x 和 y 转变成 x×y−x−y,可以看作是将 (x-1)(y-1)-1 这个数插入到堆中。最后堆中只剩下一个数,即为最终结果。以下是使用 C 语言实现的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 100000
int heap[MAX_N], heap_size;
void push(int x) {
heap[heap_size++] = x;
int i = heap_size - 1;
while (i > 0) {
int p = (i - 1) / 2;
if (heap[p] >= heap[i]) break;
int tmp = heap[p];
heap[p] = heap[i];
heap[i] = tmp;
i = p;
}
}
int pop() {
int res = heap[0];
heap[0] = heap[--heap_size];
int i = 0;
while (i * 2 + 1 < heap_size) {
int l = i * 2 + 1, r = i * 2 + 2;
int j = l;
if (r < heap_size && heap[r] > heap[l]) j = r;
if (heap[i] >= heap[j]) break;
int tmp = heap[i];
heap[i] = heap[j];
heap[j] = tmp;
i = j;
}
return res;
}
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
int x;
scanf("%d", &x);
push(x);
}
while (heap_size > 1) {
int x = pop(), y = pop();
push((x-1)*(y-1)-1);
}
printf("%d\n", heap[0]);
return 0;
}
```
注意:这里使用了一个数组来模拟堆,实际上应该使用堆的数据结构来实现。