AtCoder Beginner Contest 376

建议查看中文题面，不要问为什么*(问就是，英文题面就是复制过来的，中文体面精简些),数据范围详见题目链接

A.Candy Button

Candy Button

题目描述

There is a mysterious button. When you press this button, you receive one candy, unless less than $C$ seconds have elapsed since you last received a candy.
Takahashi decided to press this button $N$ times. He will press the button for the $i$-th time $T_i$ seconds from now.
How many candies will he receive?

一个按钮，按了会发糖。

给定多次按的时间。如果这次按的时间距离上次发糖时间超过了$c$，则发个糖。问发的糖数量。

解题思路

发糖的前提是距离上次发糖时间大于等于$c$

参考代码

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define pii std::pair<int ,int>
#define fix(x) std::fixed << std::setprecision(x)
const int inf = 1e17 + 50, MAX_N = 1e5 + 50, mod = 1e9 + 7;

void solve() {
    int n, k, ct = 0;
    std::cin >> n >> k;
    std::vector<int> a(n);
    for(int i = 0 ; i <n ; i ++) {
        std::cin >> a[i];
    }
    ct = 1;
    int pos = 0;
    for(int i = 1; i < n; i ++) {
        if(a[i] - a[pos] >= k) {
            ct ++;
            pos = i;
        }
    }

    std::cout << ct << endl;
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);
    int Lazy_boy_ = 1;
    // std::cin >> Lazy_boy_;
    while (Lazy_boy_--) solve();
    return 0;
}

B.Hands on Ring (Easy)

Hands on Ring (Easy)

题目描述

Note: This problem has almost the same setting as Problem F. Only the parts in bold in the main text and constraints differ.

You are holding a ring with both hands. This ring consists of $N\ (N \geq 3)$ parts numbered $1,2,\dots,N$, where parts $i$ and $i+1$ ($1 \leq i \leq N-1$) are adjacent, and parts $1$ and $N$ are also adjacent.

Initially, your left hand is holding part $1$, and your right hand is holding part $2$. In one operation, you can do the following:

  • Move one of your hands to an adjacent part of the part it is currently holding. However, you can do this only if the other hand is not on the destination part.

The following figure shows the initial state and examples of operations that can and cannot be made from there. The number written on each part of the ring represents the part number, and the circles labeled L and R represent your left and right hands, respectively.

You need to follow $Q$ instructions given to you in order. The $i$-th ($1 \leq i \leq Q$) instruction is represented by a character $H_i$ and an integer $T_i$, meaning the following:

  • Perform some number of operations (possibly zero) so that your left hand (if $H_i$ is L) or your right hand (if $H_i$ is R) is holding part $T_i$. Here, you must not move the other hand not specified by $H_i$.

It is guaranteed that only achievable instructions are given.

Details Under the settings of this problem, it can be proved that the positions of both hands are uniquely determined just before following the $i$-th instruction for each $i$. At that time, if we denote the positions of the left and right hands as parts $l_i$ and $r_i$, respectively, it is guaranteed that $T_i \neq r_i$ when $H_i$ is L, and $T_i \neq l_i$ when $H_i$ is R.

Find the minimum total number of operations required to follow all the instructions.

$n$的环形格子。两个棋子，初始位于$0$, $1$。
给定 $q$个指令，每个指令指定一个棋子移动到某个格子上，期间不能移动另外一个棋子。
依次执行这些指令，问移动的次数。

解题思路

简单模拟一下即可，可能我的代码有点“屎山”.

参考代码

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define pii std::pair<int ,int>
#define fix(x) std::fixed << std::setprecision(x)
const int inf = 1e17 + 50, MAX_N = 1e5 + 50, mod = 1e9 + 7;

void solve() {
    int n, q;
    std::cin >> n >> q;
    int res = 0;
    int l = 1, r = 2;
    while(q --) {
        char c;
        int x;
        std::cin >> c >> x;
        if(c == 'L' && x != l) {
            if(l < r) {
                if(x <= r) {
                    res += abs(x - l);
                }else {
                    res += (l + n - x);    
                }
            }else {
                if(x >= r) {
                    res += abs(x - l);
                }else {
                    res += (x + n - l);
                }
            }
            l = x;
        }else if(c == 'R' && x != r){
            if(l < r) {
                if(x >= l) {
                    res += abs(r - x);
                }else {
                    res += (n - r + x);
                }
            }else {
                if(x <= l) {
                    res += abs(r - x);
                }else {
                    res += (r + n - x);
                }
            }
            r = x;
        }
    }

    std::cout << res << endl;
}


signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);
    int Lazy_boy_ = 1;
    // std::cin >> Lazy_boy_;
    while (Lazy_boy_--) solve();
    return 0;
}

C.Prepare Another Box

Prepare Another Box

题目描述

There are $N$ toys numbered from $1$ to $N$, and $N-1$ boxes numbered from $1$ to $N-1$. Toy $i\ (1 \leq i \leq N)$ has a size of $A_i$, and box $i\ (1 \leq i \leq N-1)$ has a size of $B_i$.

Takahashi wants to store all the toys in separate boxes, and he has decided to perform the following steps in order:

  1. Choose an arbitrary positive integer $x$ and purchase one box of size $x$.
  2. Place each of the $N$ toys into one of the $N$ boxes (the $N-1$ existing boxes plus the newly purchased box). Here, each toy can only be placed in a box whose size is not less than the toy’s size, and no box can contain two or more toys.

He wants to execute step $2$ by purchasing a sufficiently large box in step $1$, but larger boxes are more expensive, so he wants to purchase the smallest possible box.

Determine whether there exists a value of $x$ such that he can execute step $2$, and if it exists, find the minimum such $x$.

给定 $n$个球的大小和$n - 1$个箱子的大小。现买一箱子，要求尺寸最小，使得 $n$个球恰好可以放进 $n$个箱子里,一个箱子有且只能放一个球。

解题思路

要求找出箱子大小的最小值，那么我们可以先排个序，若最后一个箱子越大，可以放入的方法就越多，反之越少。那么我们怎么求找到这个值呢？我们只需要一个箱子我们可以去尝试每一个大小箱子，但是这不现实，于是就可以想到二分，可以大大减小时间复杂度，二分条件便是查看是否有球无法放入箱子。二分完成后，要检查二分后的答案是否满足题意。

参考代码

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define pii std::pair<int ,int>
#define fix(x) std::fixed << std::setprecision(x)
const int inf = 1e17 + 50, MAX_N = 1e5 + 50, mod = 1e9 + 7;

void solve() {
    int n;
    std::cin >> n;
    std::vector<int> a(n), b(n - 1);
    for(int i = 0; i < n; i ++) {
        std::cin >> a[i];
    }

    for(int i = 0; i < n - 1; i ++) {
        std::cin >> b[i];
    }

    std::sort(a.begin(), a.end());
    std::sort(b.begin(), b.end());
    std::function<bool(int)> check = ([&](int x) -> bool {
        auto t = b;
        t.push_back(x);
        std::sort(t.begin(), t.end());
        for(int i = 0 ; i < n ; i ++) {
            if(a[i] > t[i]) return false;
        }
        return true;
    });

    int l = 1, r = inf;
    while(l < r) {
        int mid = (l + r) >> 1;
        if(check(mid)) {
            r = mid;
        }else {
            l = mid + 1;
        }
    }
    if(l == inf) {
        std::cout << -1 << endl;
    }else{ 
        std::cout << l << endl;
    }
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);
    int Lazy_boy_ = 1;
    // std::cin >> Lazy_boy_;
    while (Lazy_boy_--) solve();
    return 0;
}

D.Cycle

Cycle

题目描述

There is a simple directed graph with $N$ vertices numbered from $1$ to $N$ and $M$ edges. The $i$-th edge $(1 \leq i \leq M)$ is a directed edge from vertex $a_i$ to vertex $b_i$.
Determine whether there exists a cycle that contains vertex $1$, and if it exists, find the minimum number of edges among such cycles.

给定一张有向图，问包含点$1$的环的最小环点数。

解题思路

要确保点数最小,且有回路，那么只有 $BFS$,从点 $1BFS$，每次到达点$1$时更新答案。

参考代码

#include<bits/stdc++.h>

#define int long long
#define endl '\n'
#define pii std::pair<int ,int>
#define fix(x) std::fixed << std::setprecision(x)
const int inf = 1e17 + 50, MAX_N = 1e5 + 50, mod = 1e9 + 7;

void solve() {
  int n, m;
  std::cin >> n >> m;
  std::vector a(n + 1, std::vector<int>());

  for(int i = 0; i < m; i++) {
    int u, v;
    std::cin >> u >> v;
    a[u].push_back(v);
  }

  std::vector<int> dis(n + 1, -1ll);
  std::queue<int> q;
  dis[1] = 0;
  q.push(1);
    int res = inf;
  while (q.size()) {
    auto t = q.front();
    q.pop();
    for(auto i : a[t]) {
      if(i == 1) {
        res = std::min(res, dis[t] + 1);
      }
      if(dis[i] == -1) {
        dis[i] = dis[t] + 1;
        q.push(i);
      }	
    }
  }
  if(res > n) {
    std::cout << -1 << endl;
  }else {
    std::cout << res << endl;
  }
}

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr), std::cout.tie(nullptr);
  int Lazy_boy_ = 1;
  // std::cin >> Lazy_boy_;
  while (Lazy_boy_--) solve();
  return 0;
}

E.Max × Sum

Max × Sum

题目描述

You are given sequences of length $N$: $A = (A_1, A_2, \dots, A_N)$ and $B = (B_1, B_2, \dots, B_N)$.
Let $S$ be a subset of $\lbrace1, 2, \dots, N\rbrace$ of size $K$. Here, find the minimum possible value of the following expression:
$\displaystyle \left(\max_{i \in S} A_i\right) \times \left(\sum_{i \in S} B_i\right).$
You are given $T$ test cases; solve each of them.

给定$n$, $k$和两数组 $A$,$B$，$S$是大小为 $k$ 的 ${1,2,…,N}$ 的子集,求 $\max_{i \in S} A_{i} * \sum_{i \in S}B_{i}$ 的最小值。

解题思路

枚举$A_{i}$，剩下的问题就是找满足 $A_{j} \le A_{i}$的前$k-1$小的$B_{j}$的和。首先对数组 $A$进行排序，并且数组$B$与数组$A$一同变化（可以用pair）。然后依次枚举 $A_{i}$，此即为$\max_{i \in S} A_{i}$。然后找$1 \le j \le i$中最小的$k - 1$个$B_{i}$。考虑如何维护前 $k-1$小的和，因为会有不断的$B_{i}$加入，会不断淘汰较大的$B_{i}$，因此可以用优先队列维护这些 $B_{i}$在优先队列不断 push,pop时维护其里面的值的和即可。其时间复杂度为$O(n \log n)$注意枚举$A_{i}$时， $B_{i}$是一定要选的，因此要从优先队列里求出前$k - 1$小的和（但第$k$小的不能丢弃，它可能比$B_{i}$小，只是因为此时 $B_{i}$必选，因而暂时不能选它）。

参考代码

#include<bits/stdc++.h>

#define int long long
#define endl '\n'
#define pii std::pair<int ,int>
#define fix(x) std::fixed << std::setprecision(x)
const int inf = 1e17 + 50, MAX_N = 1e5 + 50, mod = 1e9 + 7;

void solve() {
  int n, k;
  std::cin >> n >> k;

  std::vector<std::pair<int, int> > a(n);
  for(int i = 0; i < n; i++) {
    std::cin >> a[i].first;
  }

  for(int i = 0; i < n; i++) {
    std::cin >> a[i].second;
  }


  std::sort(a.begin(), a.end(), [&](pii aa, pii bb) {
    return aa.first < bb.first;
  });

  int s = 0;
  std::priority_queue<int, std::vector<int>, std::less<> > pq;
  for(int i = 0; i < k; i++) {
    pq.push(a[i].second);
    s += a[i].second;
    }

    int res = s * a[k - 1].first;
  for(int i = k; i < n; i++) {
    auto [x, y] = a[i];

    if (y < pq.top()) {
      s -= pq.top();
      pq.pop();
      pq.push(y);
      s += y;
    }

    res = std::min(res, s * x);
  }

  std::cout << res << endl;
}

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr), std::cout.tie(nullptr);
  int Lazy_boy_ = 1;
  std::cin >> Lazy_boy_;
  while (Lazy_boy_--) solve();
  return 0;
}