CF1698B Rising Sand 题解

· · 题解

题目传送门（CF）

题目分析

给出一个数组 a，太大的数被定义为 a_i>a_{i-1}+a_{i+1}，再给出一个区间长度 k，你可以让区间长度 k 的 a_i+1 询问执行任意次操作止之后可以获得最大的过高的堆数。 计算答案是满足 a_i>a_{i-1}+a_{i+1}，当我们发现 k≥2 的时候分难改变或者十分难增加答案。因此可以看出不操作是最好的。而对于 k = 1 的情况，我们可以知道因为是任意次操作。

n 为奇数: a_2>a_1+a_3,a_4>a_3+a_5,......,a_{n-1}>a_{n-2}+a_n

n 为偶数: a_2>a_1+a_3,a_4>a_3+a_5,......,a_{n-2}>a_{n-3}+a_{n-1}

所以最多有 \frac{n-2}{2}，不计算端点。

AC Code

#include<bits/stdc++.h> //万能头文件，听说NOIP都可以用哦~
using namespace std;
const int MAX = 1000010;
int n, k, a[MAX], cnt;
int main() {
    int T;
    cin >> T;
    while (T--) {
        cin >> n >> k;
        cnt = 0;    //cnt不清零会WA
        for (int i = 1; i <= n; i++) cin >> a[i];   //n个数的读入
        if (k != 1) {   //k！=1的情况
            for (int i = 2 ; i < n ; i ++ )
                if (a[i] > a[i - 1] + a[i + 1]) cnt++;  //需要满足条件a[i]>a[i-1]+a[i+1]
        } else {    //k等于1的情况，按奇偶性分类
            if (n & 1) cnt = (n - 2) / 2 + 1;   //不会计算端点
            else cnt = (n - 2) / 2;
        }
        cout << cnt << endl;    //输出结果
    }
    return 0;
}

该题解与此处同时发布