[二分] hihoCoder 1269 优化延迟

题目大意

题目链接，通过大小为 \(k\) 的缓冲区按从大到小排序的权值小于\(q\) 的最小缓冲区大小。$ n \leq 1000000 $。

算法思路

对于每个 \(k\) 求出总延迟的过程为，使用大小为 \(k\) 的优先队列不断插入删除，时间复杂度为 \(O(n \log k )\)，如果直接枚举 \(k=1...n\)会超时，自然想到利用二分降低时间，复杂度约为 $ O(n \log n \log n )$。

算法代码

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;

int data[100005];  // 输入数据
int sd[100005];    // 排序后数据，用来求缓冲区为n时的最小值
int n;             // 数组大小
long long int q;   // 阈值

bool func(int k)  // 检查 缓冲区 大小为k时是否满足
{
    int cur = 1;
    long long int ans = 0;
    priority_queue<int> pq;
    for (int i = 0; i < n; i++) {
        if (i < k) {
            pq.push(data[i]);
        }
        else {
            ans += (cur++)*pq.top();
            pq.pop();
            pq.push(data[i]);
        }
    }

    while (!pq.empty()) {
        ans += (cur++)*pq.top();
        pq.pop();
    }

    return ans <= q;
}

int main()
{
    scanf("%d %lld", &n, &q);
    for (int i = 0; i < n; i++) {
        scanf("%d", data + i);
    }
    memcpy(sd, data, sizeof(int)*n);
    sort(sd, sd + n);

    long long int minq = 0, maxq = 0;
    for (int i = 0; i < n; i++) {
        minq += (n - i)*sd[i];           // 缓冲区为n
        maxq += (i + 1)*data[i];         // 缓冲区为1
    }

    if (minq > q) {       // k=n
        printf("-1\n");
    }
    else if (maxq <= q) { // k=1
        printf("1\n");
    }
    else {
        int a = 1, b = n;  // k in (a,b]
        while (b > a+1) {
            int mid = (a + b) / 2;
            if (func(mid)) {
                b = mid;
            }
            else {
                a = mid;
            }
        }
        printf("%d\n", b);
    }
    return 0;
}
                

转载于:https://www.cnblogs.com/lessmore/p/hihocoder-1269.html