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

日付: 11月 20, 2018

[Problem - 1070E - Codeforces](https://codeforces.com/contest/1070/problem/E)
## Problem
Given <math><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math>n tasks, each takes <math><semantics><mrow><msub><mi>P</mi><mi>i</mi></msub></mrow><annotation encoding="application/x-tex">P_i</annotation></semantics></math>Pi minutes to finish. You can choose a parameter <math><semantics><mrow><mi>d</mi></mrow><annotation encoding="application/x-tex">d</annotation></semantics></math>d and do these tasks in order. Only do tasks such that <math><semantics><mrow><msub><mi>P</mi><mi>i</mi></msub><mo>≤</mo><mi>d</mi></mrow><annotation encoding="application/x-tex">P_i \le d</annotation></semantics></math>Pi≤d, and for every consecutive <math><semantics><mrow><mi>m</mi></mrow><annotation encoding="application/x-tex">m</annotation></semantics></math>m tasks done, you have to rest for the same time of doing these <math><semantics><mrow><mi>m</mi></mrow><annotation encoding="application/x-tex">m</annotation></semantics></math>m tasks. Calculate the maximum number of tasks that can be done within <math><semantics><mrow><mi>t</mi></mrow><annotation encoding="application/x-tex">t</annotation></semantics></math>t minutes. There are <math><semantics><mrow><mi>c</mi></mrow><annotation encoding="application/x-tex">c</annotation></semantics></math>c test cases.

**Constraints**: <math><semantics><mrow><mn>1</mn><mo>≤</mo><mi>c</mi><mo>≤</mo><mn>5</mn><mo>⋅</mo><mn>1</mn><msup><mn>0</mn><mn>4</mn></msup><mo separator="true">,</mo><mn>1</mn><mo>≤</mo><mi>n</mi><mo>≤</mo><mn>2</mn><mo>⋅</mo><mn>1</mn><msup><mn>0</mn><mn>5</mn></msup><mo separator="true">,</mo><mn>1</mn><mo>≤</mo><mi>m</mi><mo>≤</mo><mn>2</mn><mo>⋅</mo><mn>1</mn><msup><mn>0</mn><mn>5</mn></msup><mo separator="true">,</mo><mn>1</mn><mo>≤</mo><mi>t</mi><mo>≤</mo><mn>4</mn><mo>⋅</mo><mn>1</mn><msup><mn>0</mn><mn>10</mn></msup><mo separator="true">,</mo><mn>1</mn><mo>≤</mo><msub><mi>P</mi><mi>i</mi></msub><mo>≤</mo><mn>2</mn><mo>⋅</mo><mn>1</mn><msup><mn>0</mn><mn>5</mn></msup></mrow><annotation encoding="application/x-tex">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</annotation></semantics></math>1≤c≤5⋅104,1≤n≤2⋅105,1≤m≤2⋅105,1≤t≤4⋅1010,1≤Pi≤2⋅105

## Solution
It can be easy to observe that number of tasks can be done will first increase and then dicrease if we increase <math><semantics><mrow><mi>d</mi></mrow><annotation encoding="application/x-tex">d</annotation></semantics></math>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 <math><semantics><mrow><msub><mi>m</mi><mn>1</mn></msub></mrow><annotation encoding="application/x-tex">m_1</annotation></semantics></math>m1 or <math><semantics><mrow><msub><mi>m</mi><mn>2</mn></msub></mrow><annotation encoding="application/x-tex">m_2</annotation></semantics></math>m2 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 <math><semantics><mrow><mi>S</mi></mrow><annotation encoding="application/x-tex">S</annotation></semantics></math>S, and check whether <math><semantics><mrow><mi>S</mi></mrow><annotation encoding="application/x-tex">S</annotation></semantics></math>S can be reached. It is easy to observe that the optimal <math><semantics><mrow><mi>d</mi></mrow><annotation encoding="application/x-tex">d</annotation></semantics></math>d is the minimal one such that the number of tasks not greater than <math><semantics><mrow><mi>d</mi></mrow><annotation encoding="application/x-tex">d</annotation></semantics></math>d is at least <math><semantics><mrow><mi>S</mi></mrow><annotation encoding="application/x-tex">S</annotation></semantics></math>S. We can find such optimal <math><semantics><mrow><mi>d</mi></mrow><annotation encoding="application/x-tex">d</annotation></semantics></math>d with **fenwick tree** and another binary search. Calculating the number of tasks under this <math><semantics><mrow><mi>d</mi></mrow><annotation encoding="application/x-tex">d</annotation></semantics></math>d can be solved by simulating the process, denoted by <math><semantics><mrow><mi>T</mi></mrow><annotation encoding="application/x-tex">T</annotation></semantics></math>T. If <math><semantics><mrow><mi>T</mi><mo>≥</mo><mi>S</mi></mrow><annotation encoding="application/x-tex">T \ge S</annotation></semantics></math>T≥S, then <math><semantics><mrow><mi>S</mi></mrow><annotation encoding="application/x-tex">S</annotation></semantics></math>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)

コメント

コメントを投稿