D小红的矩阵构造

二分数组的最大值。 利用公式需要的最小操作次数为

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
long long a[N], n, k, x;
bool check(long long mid)
{
    long long num = 0;
    for (int i = 1; i <= n; i ++) // 在a[i]大于最大值时, 总共所需操作量计数加上
        if (a[i] > mid)
            num += (a[i] - mid + x - 1) / x;// 统计所需操作量? ?可用ceil()代替操作(注意类型转换)
  		  //num += ceil(doule(a[i] - mid) / (double)x);
    return num <= k; // 如果所需最小操作量小于题目标准，代表可行。否则不可行
}

int main()
{
    int i;
    ios::sync_with_stdio(false);
    cin >> n >> k >> x;
    for (i = 1; i <= n; i ++) cin >> a[i];// 输入
    sort(a + 1, a + n + 1); // 排序，成为由小到大的有序状态
    long long l = a[1] - k * x, r = a[n], ans; // 利用二分， 分段求解
    while(l <= r)
    {
        long long mid = (l + r) >> 1; // 求取中间量
        if (check(mid)) ans = mid, r = mid - 1; //如果可行，则计入ans 并移动指针计算当mid更小时是否可行
        else l = mid + 1;
    }
    cout << ans << endl;
    //总体利用二分查找验证最小的最大值为多少

    return 0;
}