A - Daily Cookie
题意
给定长为\(n\)的串，“.”代表空，“@”代表饼干，一天吃一块饼干，问\(d\)天后有几个格子是空的。
思路
模拟。
代码
点击查看代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
const int mxn = 1e6 + 5;
void solve()
{
int n, d;
string s;
cin >> n >> d >> s;
int cnt = count(s.begin(), s.end(), '@');
cout << s.size() - (cnt - d) << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T = 1;
//cin >> T;
while (T--)
{
solve();
}
return 0;
}
B - Daily Cookie 2
题意
题意同\(A\)，每天吃最右边的饼干，输出最后的情况。
思路
模拟。
代码
点击查看代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
const int mxn = 1e6 + 5;
void solve()
{
int n, d;
string s;
cin >> n >> d >> s;
int cnt = 0;
for (int i = s.size() - 1; i >= 0; i--)
{
if (s[i] == '@')
{
s[i] = '.';
cnt++;
if (cnt == d)
{
cout << s << endl;
return;
}
}
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T = 1;
//cin >> T;
while (T--)
{
solve();
}
return 0;
}
C - Kaiten Sushi
题意
\(n\)个寿司，第\(i\)个寿司有美味度\(b_i\)；\(m\)个人，第\(i\)个人有标准\(a_i\)。将寿司放在传送带上，当第\(i\)个人面前经过寿司\(j\)且\(a_i \ge b_j\)，他会把寿司吃掉，否则什么都不做。问每个寿司被几号人吃掉，没人吃就输出\(-1\)。
思路
容易发现，当一个人\(i\)前边有人\(j\)且\(a_i \ge a_j\)时，\(i\)永远吃不到寿司，因此能吃到寿司的人就是原序列中的递减子序列。而人的顺序是不能变的，那就将寿司降序排序，如果一个人吃不了当前的寿司，那后边的他都吃不了(a_i < b_j)，就看下一个人。
代码
点击查看代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
const int mxn = 1e6 + 5;
int n, m;
vector<pii> b;
int _get(int x)
{
int l = 0, r = m;
while (l <= r)
{
int mid = l + r >> 1;
if (b[mid].first >= x)
{
l = mid + 1;
}
else
{
r = mid - 1;
}
}
return l;
}
void solve()
{
cin >> n >> m;
vector<int> a(n), ans(m, -1);
vector<pii> A;
b.resize(m);
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
int minn = a[0];
A.push_back({ a[0], 1 });
for (int i = 1; i < n; i++)
{
if (a[i] < minn)
{
minn = a[i];
A.push_back({ a[i], i + 1 });
}
}
for (int i = 0; i < m; i++)
{
cin >> b[i].first;
b[i].second = i;
}
sort(b.begin(), b.end(), greater<pii>());
int now = 0;
for (int i = 0; i < A.size(); i++)
{
int p = _get(A[i].first);
for (int j = now; j < p; j++)
{
ans[b[j].second] = A[i].second;
}
now = p;
}
for (int i = 0; i < m; i++)
{
cout << ans[i] << endl;
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T = 1;
// cin >> T;
while (T--)
{
solve();
}
return 0;
}
D -
题意
思路
代码
点击查看代码
E -
题意
思路
代码
点击查看代码