@[TOC]
比赛链接 ： Codeforces Round #797 (Div. 3)
只写了前五题，F、G题还不是很理解。
A. Print a Pedestal (Codeforces logo?)
题目：
题目大意：将一个数n，分成三个不同的整数，并且三个数中的最大那个数要最小
思路：构造+贪心
为了让最大值最小，首先将n等分为三份a=b=c=n/3;然后让a加1，c减一，这样三个数都不相同，然后再看剩下有几个，如果n只剩下一个，那么就只能加到a上，如果有两个，那么a和b分别加1个。这样就能使最大的数最小
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> PII;
typedef priority_queue<int, vector<int>, less<int>> Q;
#define x first
#define y second
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
const int N = 2e5 + 10;
int n;
void solve()
{
cin >> n;
int a, b, c;
a = b = c = n / 3;
b++;
c--;
if (n % 3 == 1)
{
b++;
}
else if (n % 3 == 2)
{
b++;
a++;
}
cout << a << " " << b << " " << c << endl;
return;
}
signed main()
{
// freopen("in.in", "r", stdin);
// freopen("out.out", "w", stdout);
int t;
cin >> t;
while (t--)
solve();
return 0;
}B. Array Decrements
题目：
题目大意：一个数组a，每次操作能让a数组中的每个元素减1，0就不用再减了。问从a通过多少次操作能让a变成b数组
思路：贪心
如果a的元素比b对应的元素小，那么一定不能变成b数组因为0操作后不变。所以先查询a数组中每个元素变成b最大的次数，那么其他每个元素需要变成b都需要最大的操作次数，看其他的元素操作完之后是否等于b数组对应的元素即可
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> PII;
typedef priority_queue<int, vector<int>, less<int>> Q;
#define x first
#define y second
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
const int N = 5e4 + 10;
int n;
int a[N], b[N];
void solve()
{
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= n; i++)
cin >> b[i];
int k = 0;
for (int i = 1; i <= n; i++)
{
if (a[i] < b[i])
{
puts("NO");
return;
}
k = max(k, a[i] - b[i]);
}
for (int i = 1; i <= n; i++)
{
a[i] = max(0, a[i] - k);
if (a[i] != b[i])
{
puts("NO");
return;
}
}
puts("YES");
return;
}
signed main()
{
// freopen("in.in", "r", stdin);
// freopen("out.out", "w", stdout);
int t;
cin >> t;
while (t--)
solve();
return 0;
}C.Restoring the Duration of Tasks
题目：
题目大意：
思路：贪心+队列
我们知道了每个任务的起始时间和结束时间，需要记录一个当前已经进行到哪个时间，我们可以枚举每个任务，当前任务的起始时间比记录的时间大的话，当前时间就为这个起始时间，如果小的话，当前时间不变，每个任务的结束时间减去当前时间就是这个任务的执行时间了。然后在把当前时间为更新为结束时间。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef priority_queue<int, vector<int>, less<int>> Q;
#define x first
#define y second
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
const int N = 2e5 + 10;
int n;
PII a[N];
int c[N];
void solve()
{
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i].x;
for (int i = 1; i <= n; i++)
cin >> a[i].y;
int time = 0; //当前时间
for (int i = 1; i <= n; i++)
{
time = max(time, a[i].x);
c[i] = a[i].y - time;
time = a[i].y;
}
for (int i = 1; i <= n; i++)
{
cout << c[i] << " ";
}
cout << endl;
return;
}
signed main()
{
// freopen("in.in", "r", stdin);
// freopen("out.out", "w", stdout);
int t;
cin >> t;
while (t--)
solve();
return 0;
}D. Black and White Stripe
题目：
题目大意：
思路：双指针
枚举每个长度为k的区间，记录这个区间中黑色格子的数量，k减去它就是最少染色数，最后所有长度为k的区间的染色数取最小值即可。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> PII;
typedef priority_queue<int, vector<int>, less<int>> Q;
#define x first
#define y second
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
const int N = 2e5 + 10;
int n, k;
char s[N];
void solve()
{
int ans = 1e9;
cin >> n >> k;
scanf("%s", s + 1);
int l = 1;
int cnt = 0;
for (int i = 1; i <= n; i++)
{
cnt += s[i] == 'B';
if (i - l + 1 == k)
{
ans = min(ans, k - cnt);
cnt -= s[l++] == 'B';
}
}
cout << ans << endl;
return;
}
signed main()
{
// freopen("in.in", "r", stdin);
// freopen("out.out", "w", stdout);
int t;
cin >> t;
while (t--)
solve();
return 0;
}E. Price Maximization
题目：
题目大意：
思路：贪心+双指针
为了能够让总价值最大，那么向下取整的时候能少失去一部分就少失去一部分，让更多的价值不能因为向下取整而失去。每个数都除于k，所以我们只需要考虑每个数求余k的部分，因为能够整除的一定会被计算上，我们只需要考虑不能被整除的即可。
因为是两个数相加一起除，所以如果存在两个余数加起来大于等于k，那么就会有更多的价值。为了又更多的价值，需要让大的余数尽量加上小的余数。
为此我们可以先将所有的余数排个序，然后利用双指针即可。
（我写的时候交了三遍才过，而且写的很复杂，写了快一个小时，首先是没想到只看余数就可以了，我是记录每个相同余数的值，然后模拟操作，所以也没想到双指针）
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> PII;
typedef priority_queue<int, vector<int>, less<int>> Q;
#define x first
#define y second
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
const int N = 2e5 + 10;
int n, k;
vector<int> v[1010];
void solve()
{
ll ans = 0;
cin >> n >> k;
vector<int> v;
for (int i = 1; i <= n; i++)
{
int a;
cin >> a;
ans += a / k;
v.push_back(a % k);
}
sort(v.begin(), v.end());
for (int i = 0, j = n - 1; i < j; i++, j--)
{
while (i < j && v[i] + v[j] < k)
i++;
if (i == j)
break;
ans++;
}
cout << ans << endl;
return;
}
signed main()
{
// freopen("in.in", "r", stdin);
// freopen("out.out", "w", stdout);
int t;
cin >> t;
while (t--)
solve();
return 0;
}加油，继续练！
