Educational Codeforces Round 158 (Rated for Div. 2)
基本情况
A题很水,几分钟秒了。
B题想到一个解,被自己 hack
掉之后没有重新想,一直想在自己一开始的基础上改好,结果最后B都没拿下。
B. Chip and Ribbon
我的思路
其实也是找规律,根本没严谨地证明正确性。不应该一条路走到黑的。
找到第一个比上一个小的数,再找到最后一个这样的数,求两者差值。
毫无逻辑,就只是刚好通过样例了,我手造一堆数据 hack
了。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2e5 + 10;
int t, n;
long long ans = 0, cnt;
int c[N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> t;
while (t--)
{
int l = 0;
ans = 0;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> c[i];
if (c[i] && !l)
l = i;
}
if (n == 1)
{
cout << c[1] - 1 << endl;
}
else
{
if (l != 1)
{
ans++;
}
bool is_end = true;
bool is_cnt = false;
for (int i = l + 1; i <= n; i++)
{
int temp = c[i - 1];
if (i - 1 == l && c[i - 1] == 1)
{
if (c[i] < c[i - 1])
is_cnt = true;
continue;
}
while (c[i] < c[i - 1])
{
is_cnt = true;
i++;
if (i == n + 1)
{
is_end = false;
break;
}
}
ans += temp - c[i - 1];
}
if (is_end)
{
if (!(ans == 1 && l != 1 && !is_cnt))
{
ans += c[n];
}
}
cout << ans << endl;
}
}
return 0;
}
正解思路
At first, let's change the statement a bit: instead of teleporting our chip into cell \(x\), we create a new chip in cell \(x\) (it means that the chip does not disappear from the cell where it was located). And when we want to move a chip, we move any chip to the next cell. Then, \(c_i\) will be the number of times a chip appeared in the cell \(i\), and the problem will be the same: ensure the condition on each \(c_i\) by "creating" the minimum number of chips.
Let's look at value of \(c_1\). If \(c_1>1\), we have to create at least \(c_1−1\) new chips in cell \(1\). Let's create that number of chips in that cell.
Then, let's see how we move chips from the cell \(i\) to the cell \((i+1)\). If \(c_i≥c_{i+1}\), then all chips that appeared in the cell \((i+1)\) could be moved from the \(i\)-th cell, so we don't need to create any additional chips in that cell.
But if \(c_i<c_{i+1}\), then at least \(c_{i+1}−c_i\) chips should be created in the cell \((i+1)\), since we can move at most \(c_i\) chips from the left.
So, for every \(i\) from \(2\) to \(n\), we have to create \(\max(0, c_i - c_{i-1})\) chips in the \(i\)-th cell; and the number of times we create a new chip in total is
\[c_1 - 1 + \sum\limits_{i=2}^{n} \max(0, c_i - c_{i-1}) \]#include <bits/stdc++.h>
using namespace std;
const int N = 200'000;
int t;
int main() {
cin >> t;
for (int tc = 0; tc < t; ++tc) {
int n;
cin >> n;
vector <int> cnt(n);
long long res = 0;
int cur = 0;
for (int i = 0; i < n; ++i) {
cin >> cnt[i];
if (cnt[i] > cur)
res += cnt[i] - cur;
cur = cnt[i];
}
cout << res - 1 << endl;
}
return 0;
}
标签:Educational,Rated,int,158,chip,cnt,cell,chips,create
From: https://www.cnblogs.com/kdlyh/p/17856539.html