社区讨论
贪心+模拟 这思路行不行AC 但是感觉是不是有反例?
P14665[KenOI 2025] 序列题参与者 3已保存回复 4
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 4 条
- 当前快照
- 1 份
- 快照标识符
- @mj2ovjbq
- 此快照首次捕获于
- 2025/12/12 17:53 2 个月前
- 此快照最后确认于
- 2025/12/14 10:50 2 个月前
CPP
#include <bits/stdc++.h>
using namespace std;
int n, m, a[5010];
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
int mx = a[1];
for (int i = 1; i <= n; i++) {
mx = max(mx, a[i]);
}
// 找到最后一个最大值的下标
int lastMaxPos = 0;
for (int i = 1; i <= n; i++) {
if (a[i] == mx) {
lastMaxPos = i;
}
}
if (lastMaxPos != n) {
int temp[5010];
int idx = 1;
// 1. 先将最后一个最大值后面的部分复制到开头
for (int i = lastMaxPos + 1; i <= n; i++) {
temp[idx++] = a[i];
}
// 2. 再将第一个元素到最后一个最大值之间的部分接上
for (int i = 1; i <= lastMaxPos; i++) {
temp[idx++] = a[i];
}
// 3. 将结果复制回原数组
for (int i = 1; i <= n; i++) {
a[i] = temp[i];
}
}
//预处理 将其拼接成最大环 例如 [1, 2, 3, 4, 1, 1, 4, 1, 1]--> [1, 1 ,1, 2, 3, 4, 1, 1, 4]
//找到最后一个最大值,将其放在最前面
for (int op = 0; op < m; op++) {
// 找到当前最小值和最大值
int mn = a[1];
for (int i = 1; i <= n; i++) {
mn = min(mn, a[i]);
}
//cout << "最小值:" << mn << "\n";
// 如果已经全部相等,可以提前结束
if (mn == mx) break;
//寻找包含最小值的子段
int l = 1,r = 1;
bool f = false;
for(int i = 1; i <= n ; i++){
if(a[i] == mn) f = true;
if(a[i] == mx){ //遇到最大值,停止
//并且 有包含最小值
if(f){
r = i - 1;
break;
}else{
l = i + 1;
continue;
}
}
}
for(int i = l ; i <= r; i++){
a[i]++;
}
}
//
// // 计算最终极差
int mn = a[1];
mx = a[1];
for (int i = 1; i <= n; i++) {
mn = min(mn, a[i]);
mx = max(mx, a[i]);
}
cout << mx - mn << endl;
return 0;
}
如题,思路是贪心,如果把数据当作一个环,那么增加一个区域等于减少一个区域,既然如此那我就拼接数组
例如:[1, 2, 3, 4, 1, 1, 4, 1, 1]--> [1, 1 ,1, 2, 3, 4, 1, 1, 4] ,把最后一个最大值开始的数据都移动到最前面,然后开始找子段,有包含最小值的子段就统一+1,执行m次,最后统一看一次极差即可。 思路有没有错,能不能给点建议
回复
共 4 条回复,欢迎继续交流。
正在加载回复...