情况
时间：2024年7月17日12:50-14:50
题解
A
思路
数学
代码
1
2
3
4
5
6
| void solve()
{
int n, k;
cin >> n >> k;
cout << (n - 1) * k + 1 << endl;
}
|
B
题意
您将获得一个长度为 n 的整数数组 a
您可以应用以下操作任意次数（可能为零）：
- 首先，选择一个整数 k ，使得 1≤k≤n 并支付 k+1 硬币。
- 然后，精确地选择 k 索引，使得 1≤i1<i2<…<ik≤n 。
- 然后，对于从 1 到 k 的每个 x ，将 aix增加 1 。
求出使 a 不递减所需的最小硬币数
思路
贪心，找出要加的，和顺序没啥关系。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| void solve()
{
int n;
vector<int> a;
vector<int> b;
cin >> n;
int x;
cin >> x;
a.push_back(x);
int max = x;
int temp = 0;
for (int i = 1; i < n; i++)
{
int x;
cin >> x;
a.push_back(x);
if (a[i] < max)
{
int cha = max - a[i];
b.push_back(cha);
}
else
{
max = a[i];
}
}
sort(b.begin(), b.end());
LL ans = 0;
LL sunhao = 0;
for (int i = 0; i < b.size(); i++)
{
if (b[i] - sunhao > 0)
{
ans += (b.size() - i + 1) * (b[i] - sunhao);
sunhao = b[i];
}
}
cout << ans << endl;
}
|
C
题意
一行中有 n朵花，其中第 i𝑖 朵最初具有 hi 米的正高度。
每隔一秒，风就会从左边吹来，导致一些花的高度降低。
具体地，每秒，对于从 1 到 n 的每个 i ，按照这个顺序，发生以下情况：
- 如果是 i=n或 hi>hi+1 ，则 hi 的值变为 max(0,hi−1)。
在所有的 1≤i≤n第一次出现之前， hi=0 会经过多少秒？
思路
简单dp，关注到达0的时间，前面的由后面的决定。但一直没写好。浪费时间。因为没分割子问题。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| void solve()
{
int n;
cin >> n;
if (n == 1)
{
int ans1 = 0;
cin >> ans1;
cout << ans1 << endl;
return;
}
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
LL ans = 0;
for (int j = n; j >= 1; j--)
{
if (a[j] <= ans)
{
ans++;
}
else
{
ans = a[j];
}
}
cout << ans << endl;
}
|
