CF218A Mountain Scenery 题解

题意简述

给定两个整数 $n,k$。

再给定一个长度为 $2 \times n +1$ 的数列，这个数列的第偶数项 $a_i$ 满足 $a_i > a_{i-1}, a_i > a_{i+1}$。

想在将这个数列的 $k$ 个偶数项删去 $1$（不能重复）且这个数列仍然满足原数列的条件，输出这个数列。

解题思路

我们可以从 $1$ 到 $2 \times n + 1$ 扫一遍，如果遇到偶数项且这个偶数项 $a_i$ 满足 $a_i > a_{i-1} + 1 , a_i>a_{i+1}+1$，就将 $k$ 减 $1$，直到 $k=0$。

之所以要满足 $a_i > a_{i-1} + 1 , a_i>a_{i+1}+1$ 而不是 $a_i > a_{i-1}, a_i > a_{i+1}$，是因为这个偶数项将要减 $1$，就有可能出现 $a_i = a_{i-1}$ 或 $a_i > a_{i+1}$ 的情况，这样就不满足题意了。

本题有 spj。

代码实现

#include<bits/stdc++.h>
using namespace std;
int n,k,a[1000005];
int main() {
	scanf("%d%d",&n,&k); n=2*n+1;
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=2;i<=n;i+=2) {
		if(k==0) break;
		if(a[i]>a[i-1]+1&&a[i]>a[i+1]+1) a[i]--,k--;
	}
	for(int i=1;i<=n;i++) printf("%d ",a[i]);
	return 0;
}
//code by TheCedar