💭Codeforces Round 980 (Div. 2)

A. Profitable Interest Rate

题意

有两种储值方式——无利可图和盈利，“盈利”可以保证盈利，但是有最低储值要求，“无利可图”类型没有利息，但是可以让“盈利”的最低储值降低。在“无利可图”储值 $x$ 元，可以让“盈利”的最低值要求降低 $2\times x$ 元，最低储值不能低于 $0$ 元，两种储值均不能取出。现在Alice拥有 $a$ 元，并想使存入“盈利”的金额越多越好，求Alice最多存入多少“盈利”类型的金额。

数据范围

$1\leq t\leq 10^4$
$1\leq a,b\leq 10^9$

思路

假设存入 $x$ 元在“无利可图”，则“盈利”的最低储值降为 $b-2\times x$ ，此时如果Alice的剩余金额 $a-x$ 可以达到最低储值，则答案为 $a-x$ ，否则为 $0$ ，最小化 $x$ 即可。

参考代码

1
void solve() {
2
  ll a, b;
3
  cin >> a >> b;
4
  ll x = max(0ll, b - a);
5
  ll ans = max(0ll, a - x);
6
  cout << ans << '\n';
7
}

B. Buying Lemonade

题意

柠檬水售卖机有 $n$ 个按钮，但是无法辨认每个按钮对应的槽位还剩多少柠檬水，购买者知道每个槽位最初的柠檬水数量，每按下一个按钮，如果该按钮对应的槽位还有柠檬水，则可以售出 $1$ 瓶柠檬水，若槽位为空，则将没有任何东西掉出来。现在需要精确购买 $k$ 瓶柠檬水，保证柠檬水售卖机里有足够的柠檬水，即 $\sum_{i=1}^{n} a_i \ge k$ 。求问最少的可以保证达成任务的点击次数。

数据范围

$1\leq t\leq 10^4$
$1\leq n\leq 2\times 10^5$
$1\leq k\leq 10^9$
$1\leq a_i\leq 10^9$

$n$ 之和不超过 $2\times 10^5$ 。

思路

基本的贪心购买思路是一直按同一个按钮，直到该槽位为空，考虑到购买 $k$ 瓶至少需要 $k$ 次基本点击，我们需要最小化会浪费的点击次数，即点空槽位的次数。

假设当前每个槽位都至少有 $2$ 瓶柠檬水，我们想最小化点空的次数，最好先把每个按钮都点击 $2$ 次，如果此时的总数足够 $k$ ，我们就计数次数，否则去掉空槽位（通过 1 次点击去除），我们要继续最小化。

二分在每个按钮点击的次数，查询能买到的柠檬水总数，计数最少的次数，即第一个满足总数大于等于 $k$ 的那个次数。

参考代码

1
ll a[maxn];
2

3
void solve() {
4
  ll n, k;
5
  cin >> n >> k;
6
  for (ll i = 1; i <= n; i++) {
7
    cin >> a[i];
8
  }
9
  sort(a + 1, a + 1 + n);
10

11
  auto get_cnt = [&](ll cnt) {
12
    ll ret = 0ll, tot = 0ll;
13
    for (ll i = 1; i <= n; i++) {
14
      if (a[i] < cnt) {
15
        if (tot + a[i] < k) {
16
          ret += a[i] + 1;
17
          tot += a[i];
18
        } else {
19
          ret += k - tot;
20
          break;
21
        }
22
      } else {
23
        if (tot + cnt < k) {
24
          ret += cnt;
25
          tot += cnt;
26
        } else {
27
          ret += k - tot;
28
          break;
29
        }
30
      }
31
    }
32
    return ret;
33
  };
34
  auto get_lemonade = [&](ll cnt) {
35
    ll tot = 0ll;
36
    for (ll i = 1; i <= n; i++) {
37
      if (a[i] < cnt) {
38
        tot += a[i];
39
      } else {
40
        tot += cnt;
41
      }
42
    }
43
    return tot;
44
  };
45

46
  // 可以获得k的第一个次数的下标
47
  ll l = 1, r = n;
48
  while (l < r) {
49
    ll mid = l + (r - l) / 2;
50
    if (get_lemonade(a[mid]) < k) {
51
      l = mid + 1;
52
    } else {
53
      r = mid;
54
    }
55
  }
56
  ll ans = get_cnt(a[l]);
57
  cout << ans << '\n';
58
}

C. Concatenation of Arrays

题意

有 $n$ 个二元组，将这些二元组重新排序后让序列的逆序数最小，输出排序后的结果。

数据范围

$1\leq t\leq 10^4$
$1\leq n\leq 10^5$
$1\leq a_{i,j}\leq 10^9$

思路

排序，将二元组按照两数之和、第一位数、第二位数的优先级顺序从小到大排序。

参考代码

1
void solve() {
2
  ll n;
3
  cin >> n;
4
  vector<pll> v;
5
  for (ll i = 1; i <= n; i++) {
6
    pll p;
7
    cin >> p.first >> p.second;
8
    v.push_back(p);
9
  }
10
  sort(v.begin(), v.end(), [&](pll p1, pll p2) {
11
    return make_tuple(p1.first + p1.second, p1.first, p1.second) <
12
           make_tuple(p2.first + p2.second, p2.first, p2.second);
13
  });
14
  for (auto i : v) {
15
    cout << i.first << ' ' << i.second << ' ';
16
  }
17
  cout << '\n';
18
}

D. Skipping

题意

问答系统，对第 $i$ 个题，如果选择回答，可以获得 $a_i$ 分数，接下来只能选择序号 $j\lt i$ 且没有操作过的问题。也可以选择跳过，接下来可以选择 $j\leq b_i$ 的未操作过的题目。从 $1$ 号问题开始回答。

思路

注意到，当跳到索引 $i$ 时，所有 $1\leq k\leq i$ 的没有回答过的题目，都可以通过依次回答。我们只需要贪心的选择前置和-到达某个位置的最小代价即可。

考虑用一个全局 $multiset$ 维护当前可以使用的代价，从 $1$ 号问题开始，每个问题的 $b_i$ 指向一个到 $b_i+1$ 会“失效”的最小代价，每次移动时去除失效代价，并加入新的最小代价，维护最大得分即可。

维护时可以注意到 $b_i\leq i$ 的跳题没有意义，不如直接向前答题，可以通过判断去除这种移动。

参考代码

1
void solve() {
2
  cin >> n;
3
  for (ll i = 1; i <= n; i++) {
4
    cin >> a[i];
5
    pre[i] = pre[i - 1] + a[i];
6
  }
7
  for (ll i = 1; i <= n; i++) {
8
    cin >> b[i];
9
  }
10

11
  // ll ans = a[1];
12
  multiset<ll> st;        // 可行代价
13
  map<ll, vector<ll>> mp; // 存储到达i的所有可行代价
14
  mp[2].push_back(0);
15
  st.insert(0);
16
  ll ans = a[1];
17
  for (ll i = 1; i <= n; i++) {
18
    for (auto x : mp[i]) {
19
      st.erase(st.find(x)); // 删去不再适用的代价
20
    }
21

22
    if (st.empty()) {
23
      dis[i] = -1; // 没有可用的代价
24
    } else {
25
      dis[i] = *st.begin();
26
    }
27

28
    if (dis[i] == -1)
29
      continue;
30
    ans = max(ans, pre[i] - dis[i]);
31

32
    if (b[i] <= i)
33
      continue;
34
    // 可以拓展到点b[i],b[i]+1时刻这些代价都不再适用
35
    ll d = dis[i] + a[i];
36
    mp[b[i] + 1].push_back(d);
37
    st.insert(d);
38
  }
39

40
  cout << ans << '\n';
41
}