[二分] 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