题目描述

难度分:$1500$

输入$n$，$m(1 \leq n \leq m \leq 10^9)$，$k(1 \leq k \leq n)$。

有一个长为$n$的数组$a$，已知其所有元素均为正整数，元素和等于$m$且$|a[i]-a[i+1]| \leq 1$。

问：$a[k]$最大能是多少？

输入样例$1$

4 6 2

输出样例$1$

2

输入样例$2$

3 10 3

输出样例$2$

4

输入样例$3$

3 6 1

输出样例$3$

3

算法

二分答案

这个题比较容易发现单调性，因为$a[k]$越大，整个数组的元素之和越大，所以能用二分答案来做。对于某个给定的$a[k]$值，我们将其视为整个数组的峰值，从它开始向数组的两翼递减可以得到最优解。

1. 如果此时数组的累加和$s=\Sigma_{i=1}^{n}a[i] \leq m$，说明此时$a[k]$的值是可以的，记录答案并往右搜索看能不能更大。这里还有个点需要思考一下，对于某个固定的$a[k]$，如果$m \gt s$，还应该把剩下值也分配进数组，我们可以从两翼开始分配剩余的值，每次给元素增加$1$。可以发现，当二分已经使$a[k]$达到最大值时，一定能把$m-s$分配进数组而不增加$a[k]$的值。
2. 否则$a[k]$给得就太大了，应该往左搜索答案。

复杂度分析

时间复杂度

在值域范围$[1,m]$内进行二分答案，$check$是$O(1)$的，因此时间复杂度为$O(log_2m)$。

空间复杂度

整个算法过程仅使用了有限几个变量，因此额外空间复杂度为$O(1)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

int n, m, k;

LL get(LL a1, LL n, LL d) {
    LL sum = 0;
    if(a1 < 1) {
        LL cnt1 = 1 - a1;
        sum += cnt1;
        a1 = 1;
        LL an = a1 + (n - cnt1 - 1)*d;
        if(an < 1) {
            LL cnt2 = 1 - an;
            sum += cnt2;
            an = 1;
            sum += (a1 + an)*(n - cnt1 - cnt2) / 2; 
        }else {
            sum += (a1 + an)*(n - cnt1) / 2;
        }
    }else {
        LL an = a1 + (n - 1)*d;
        if(an < 1) {
            LL cnt2 = 1 - an;
            sum += cnt2;
            an = 1;
            sum += (a1 + an)*(n - cnt2) / 2;
        }else {
            sum += (a1 + an)*n / 2;
        }
    }
    return sum;
}

int main() {
    scanf("%d%d%d", &n, &m, &k);
    if(n == m) {
        puts("1");
        return 0;
    }
    int l = 1, r = m;
    while(l < r) {
        int mid = l + r + 1 >> 1;
        int a1 = mid - k + 1, ak = mid;
        if(get(a1, k, 1) + get(ak, n - k + 1, -1) - ak <= m) {
            l = mid;
        }else {
            r = mid - 1;
        }
    }
    printf("%d\n", r);
    return 0;
}