Burnling's Blog
0%

CF1698B Rising Sand

发表于 更新于 分类于 ，

题意简述

有 $n$ 堆沙子，每堆沙子的高度为 $a_i$ ，当一堆沙子的高度大于左右两堆沙子高度总和时，称这堆沙子过高。

会给出一个整数 $k$ ，你可以对这 $n$ 堆沙子进行若干次操作，使得连续 $k$ 堆沙子的高度都加 $1$ .

求若干次操作后，最多有多少堆沙子过高。

题目分析

首先考虑达到什么条件后过高的沙子堆数最多。

因为过高的某堆沙子一定高于左右两边的沙子，所以 过高的沙子左右两边的沙子一定不是过高的 。

那么，在这种条件下，最优解显然为：过高夹过低。

比如 2 9 2 4 1 这一组沙子就是当前情况的最优解。

那么就要尝试将原始的 $n$ 堆沙子变成如上情形。

考虑对 $k$ 进行分类讨论。

  1. 当 $k = 1$ 时，可以对所有的沙子进行单点修改，使得原始数据变为最优情形。

    此时的最大堆数为 $\lceil\dfrac{N}{2}\rceil - 1​$ .

  2. 当 $k>1$ 时，由于每次操作都会带上旁边的若干堆沙子一起增加高度，所以实际上增加后也无法比旁边的沙子高出很多成为过高的沙子。 （不过倒是可以变成过低的沙子）

那么最后的算法就显而易见了：判断 $k$ 是否为 $1$ ，如果为 $1$ 结果则为 $\lceil\dfrac{N}{2}\rceil - 1$ ；如果 $k\not=1$ ，结果为输入的沙堆的过高堆数。

那么为了好写一些，我们可以对每次输入都统计过高的沙堆数量，然后再判断 $k$ 与 $1$ 的关系。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
using namespace std;

int A[10];//优化了下空间，实际没有必要，还会让代码更丑（
int N,K;

inline void mov(){
    for(int i = 1;i<=5;i++){
        A[i] = A[i+1];
    }
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        
        scanf("%d%d",&N,&K);
        int cnt = 0;
        
        memset(A,0,sizeof(A));
        
        for(int i = 1;i<=N;i++){
            
            if(i >= 3){
                
                scanf("%d",&A[3]);
                if(A[1] + A[3] < A[2]) cnt++; //边读入边判断
                mov();
            }else scanf("%d",&A[i]);
        }
        
        if(K == 1) printf("%d\n",int(ceil(N / 2.0))-1);
        else printf("%d\n",cnt);
    }
    return 0;
}