Codeforces 1070E. Getting Deals Done (Binary Search+Fenwick Tree)

日付: 11月 20, 2018

[Problem - 1070E - Codeforces](https://codeforces.com/contest/1070/problem/E)
## Problem
Given $n$ tasks, each takes $P_i$ minutes to finish. You can choose a parameter $d$ and do these tasks in order. Only do tasks such that $P_i \le d$, and for every consecutive $m$ tasks done, you have to rest for the same time of doing these $m$ tasks. Calculate the maximum number of tasks that can be done within $t$ minutes. There are $c$ test cases.

**Constraints**: $1\le c \le 5\cdot 10^4, 1\le n \le 2\cdot 10^5, 1\le m \le 2\cdot 10^5, 1\le t \le 4\cdot 10^{10}, 1\le P_i \le 2\cdot 10^5$

## Solution
It can be easy to observe that number of tasks can be done will first increase and then dicrease if we increase $d$. It seems that this problem can be done with **ternary search**. However this function is not strictly incresing or decreasing, we cannot tell whether $m_1$ or $m_2$ is closer to peak point because they may be on the same side of the peak point.

We can **binary search** the number of tasks can be done, denoted as $S$, and check whether $S$ can be reached. It is easy to observe that the optimal $d$ is the minimal one such that the number of tasks not greater than $d$ is at least $S$. We can find such optimal $d$ with **fenwick tree** and another binary search. Calculating the number of tasks under this $d$ can be solved by simulating the process, denoted by $T$. If $T \ge S$, then $S$ can be reached.

## Code
```c++
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using PII = pair<int, int>;
#define FI(i,a,b) for(int i=(a);i<=(b);++i)
#define FD(i,b,a) for(int i=(b);i>=(a);--i)
#define DEBUG(x) cerr << #x << ": " << (x) << endl;
constexpr int inv(LL x, int m) { return x > m ? inv(x % m, m) : x > 1 ? inv(m % x, m) * (m - m / x) % m : x; }
constexpr int mpow(LL a, LL k, int m) { int r(1); for (a %= m; k; k >>= 1, a = a * a % m) if (k & 1)r = r * a % m; return r; }

template <typename T> struct Fenwick {
    vector<T> V;
    Fenwick(int n): V(n) {}
    void add(size_t i, T x) { for (; i < V.size(); i |= i + 1) V[i] += x; }
    T sum(int i) { T r = T(); for (--i; i >= 0; i = (i & (i + 1)) - 1) r += V[i]; return r; }
    T sum(int l, int r) { return sum(r) - sum(l); }
};

int main() {
    const int N = 2e5 + 1;
    Fenwick<int> fw(N);
    auto solve = [&]() {
        int n, m;
        LL t;
        scanf("%d%d%lld", &n, &m, &t);
        vector<int> P(n + 1);
        FI(i, 1, n) scanf("%d", &P[i]), fw.add(P[i], 1);
        auto calc = [&](LL d) {
            int tasks = 0, cnt = 0;
            LL r = t, tuse = 0;
            FI(i, 1, n) {
                if (P[i] > d) continue;
                if (r < P[i]) break;
                r -= P[i], tuse += P[i], cnt++, tasks++;
                if (cnt == m) r -= tuse, tuse = 0, cnt = 0;
            }
            return tasks;
        };
        auto check = [&](int tasks) {
            int l = 0, r = N - 1;
            while (l + 1 < r) {
                int m = (l + r + 1) >> 1;
                if (fw.sum(m + 1) >= tasks) r = m;
                else l = m;
            }
            int can = calc(r);
            if (can >= tasks) return r;
            else return -1;
        };
        int l = 0, r = n + 1;
        while (l + 1 < r) {
            int m = (l + r) >> 1;
            if (check(m) != -1) l = m;
            else r = m;
        }
        cout << l << ' ' << check(l) << endl;
        FI(i, 1, n) fw.add(P[i], -1);
    };
    int t;
    scanf("%d", &t);
    while (t--) solve();
    return 0;
}
```

KONGROOの基地

このブログを検索

Codeforces 1070E. Getting Deals Done (Binary Search+Fenwick Tree)

コメント

コメントを投稿