社区讨论

贪心+模拟 这思路行不行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 条回复,欢迎继续交流。

正在加载回复...