A. Detective Book

Description:

Ivan recently bought a detective book. The book is so interesting that each page of this book introduces some sort of a mystery, which will be explained later. The $i$-th page contains some mystery that will be explained on page $a_i$ ($a_i \ge i$).
Ivan wants to read the whole book. Each day, he reads the first page he didn't read earlier, and continues to read the following pages one by one, until all the mysteries he read about are explained and clear to him (Ivan stops if there does not exist any page $i$ such that Ivan already has read it, but hasn't read page $a_i$). After that, he closes the book and continues to read it on the following day from the next page.
How many days will it take to read the whole book?

Input:

The first line contains single integer $n$ ($1 \le n \le 10^4$) — the number of pages in the book.
The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($i \le a_i \le n$), where $a_i$ is the number of page which contains the explanation of the mystery on page $i$.

Output

Print one integer — the number of days it will take to read the whole book.

Sample Input:

9
1 3 3 6 7 6 8 8 9

Sample Output:

4

题目链接

一本书每页有一个隐藏在 $a_{i}$ 页的秘密,每天看到理解所看所有内容时停止,求看完一本书所需天数

遍历模拟即可

AC代码:

#include <bits/stdc++.h>

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0); std::cout.tie(0);

  int n; std::cin >> n;
  std::vector<int> a(n);
  for (auto &it : a) {
    std::cin >> it;
    --it;
  }

  int flag = 0, cnt = 0;
  for (int i = 0; i < n; ++i) {
    flag = std::max(flag, a[i]);
    if (flag <= i) cnt++;
  }
  
  std::cout << cnt << '\n';
  return 0;
}

B. Good String

Description:

You have a string $s$ of length $n$ consisting of only characters > and <. You may do some operations with this string, for each operation you have to choose some character that still remains in the string. If you choose a character >, the character that comes right after it is deleted (if the character you chose was the last one, nothing happens). If you choose a character <, the character that comes right before it is deleted (if the character you chose was the first one, nothing happens).
For example, if we choose character > in string > > < >, the string will become to > > >. And if we choose character < in string > <, the string will become to <.
The string is good if there is a sequence of operations such that after performing it only one character will remain in the string. For example, the strings >, > > are good.
Before applying the operations, you may remove any number of characters from the given string (possibly none, possibly up to $n - 1$, but not the whole string). You need to calculate the minimum number of characters to be deleted from string $s$ so that it becomes good.

Input:

The first line contains one integer $t$ ($1 \le t \le 100$) – the number of test cases. Each test case is represented by two lines.
The first line of $i$-th test case contains one integer $n$ ($1 \le n \le 100$) – the length of string $s$.
The second line of $i$-th test case contains string $s$, consisting of only characters > and <.

Output

For each test case print one line.
For $i$-th test case print the minimum number of characters to be deleted from string $s$ so that it becomes good.

Sample Input:

3
2
<>
3
><<
1
>

Sample Output:

1
0
0

题目链接

> 可自动消除右侧所有字符, < 可自动消除左侧所有字符,求最小删除几个字符之后字符串可自动消除到只剩下一个字符

对最左侧的 > (删除此位置左侧所有字符)和最右侧的 < (删除此位置右侧所有字符)所需删除字符取最小值

AC代码:

#include <bits/stdc++.h>

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0); std::cout.tie(0);

  int t; std::cin >> t;
  for (int cas = 0; cas < t; ++cas) {
    int n; std::cin >> n;
    std::string str; std::cin >> str;

    int l = -1, r = -1;
    for (int i = 0; i < n; ++i)
      if (str[i] == '>') {
        l = i;
        break;
      }
    for (int i = n - 1; i > 0; --i) 
      if (str[i] == '<') {
        r = i;
        break;
      }

    std::cout << std::max(0, std::min(l, n - r - 1)) << '\n';
  }
  return 0;
}

C. Playlist

Description:

You have a playlist consisting of $n$ songs. The $i$-th song is characterized by two numbers $t_i$ and $b_i$ — its length and beauty respectively. The pleasure of listening to set of songs is equal to the total length of the songs in the set multiplied by the minimum beauty among them. For example, the pleasure of listening to a set of $3$ songs having lengths $[5, 7, 4]$ and beauty values $[11, 14, 6]$ is equal to $(5 + 7 + 4) \cdot 6 = 96$.
You need to choose at most $k$ songs from your playlist, so the pleasure of listening to the set of these songs them is maximum possible.

Input:

The first line contains two integers $n$ and $k$ ($1 \le k \le n \le 3 \cdot 10^5$) – the number of songs in the playlist and the maximum number of songs you can choose, respectively.
Each of the next $n$ lines contains two integers $t_i$ and $b_i$ ($1 \le t_i, b_i \le 10^6$) — the length and beauty of $i$-th song.

Output

Print one integer — the maximum pleasure you can get.

Sample Input:

4 3
4 7
15 1
3 6
6 8

Sample Output:

78

Sample Input:

5 3
12 31
112 4
100 100
13 55
55 50

Sample Output:

10000

题目链接

每首歌有两个属性:$\texttt{length}$和 $\texttt{beauty}$ ,现可选择最多 $k$ 首歌,求最小 $\texttt{pleasure}$ ( $\texttt{pleasure}=(\sum \texttt{length}) * \min(\texttt{beauty})$ )

先将歌按照 $\texttt{beauty}$ 值降序排序,用堆维护 $\texttt{length}$ 值,遍历歌曲取 $\texttt{pleasure}$ 最大值即可(由于 $\texttt{beauty}$ 已排序,所以当前枚举值即为最小值)

AC代码:

#include <bits/stdc++.h>

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0); std::cout.tie(0);

  int n, k; std::cin >> n >> k;
  std::vector<std::pair<long long, long long>> s(n);
  for (auto &it : s) std::cin >> it.first >> it.second;
  sort(s.begin(), s.end(), [&](std::pair<long long, long long> k1, std::pair<long long, long long> k2) {
    return k1.second > k2.second;
  });

  long long sum = 0, ans = 0;
  std::priority_queue<long long, std::vector<long long>, std::greater<long long> > que;
  for (int i = 0; i < n; ++i) {
    que.push(s[i].first);
    sum += s[i].first;
    if (i >= k) {
      long long cur = que.top(); que.pop();
      sum -= cur;
    }
    ans = std::max(ans, sum * s[i].second);
  }

  std::cout << ans << '\n';
  return 0;
}

D. Minimum Triangulation

Description:

You are given a regular polygon with $n$ vertices labeled from $1$ to $n$ in counter-clockwise order. The triangulation of a given polygon is a set of triangles such that each vertex of each triangle is a vertex of the initial polygon, there is no pair of triangles such that their intersection has non-zero area, and the total area of all triangles is equal to the area of the given polygon. The weight of a triangulation is the sum of weigths of triangles it consists of, where the weight of a triagle is denoted as the product of labels of its vertices.
Calculate the minimum weight among all triangulations of the polygon.

Input:

The first line contains single integer $n$ ($3 \le n \le 500$) — the number of vertices in the regular polygon.

Output

Print one integer — the minimum weight among all triangulations of the given polygon.

Sample Input:

3

Sample Output:

6

Sample Input:

4

Sample Output:

18

题目链接

一个多边形顶点编号为 $[1,n]$ ,将多边形分为数个不相交三角形,每个三角形的权值为三个点之积,求多边形权值之和最小值

画图可发现最小值显然在以顶点 $1$ 向其它各顶点连线所分的三角形时最小

AC代码:

#include <bits/stdc++.h>

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0); std::cout.tie(0);

  int n; std::cin >> n;

  long long ans = 0;
  for (int i = 2; i < n; ++i) ans += i * (i + 1);

  std::cout << ans << '\n';
  return 0;
}
Last modification:March 29th, 2019 at 08:53 pm
如果觉得我的文章对你有用,请随意赞赏