第一题
题目: Problem - 1623A - Codeforces
题意:
数学题，给定一个n行m列的棋盘，左上角方格坐标是（1,1），然后给定一个机器人的坐标和垃圾的坐标，机器人可以清理当前格子所在的行和列，同时每秒钟向右下角移动（1,1）个方格，如果碰到了墙壁则向相反的方向移动，问多少秒后可以将垃圾清理掉。
输入格式
输入包含多组测试用例。
每组测试用例占一行，包含六个整数，分别是棋盘的行和列数，然后分别是机器人的坐标和垃圾的坐标。
输出格式
输出一个整数，代表经过多少秒可以清理垃圾。
数据范围
1≤ N ≤300
1≤ m ≤106
1≤ Ai ≤106
输入样例：
5
10 10 6 1 2 8
10 10 9 9 1 1
9 8 5 6 2 1
6 9 2 2 5 8
2 2 1 1 2 1输出样例：
7
10
9
3
0思路:
- 水题，模拟就完了。
代码:
#include<iostream>
#include<string>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int N = 10010;
int main()
{
int k;
cin >> k;
while (k--)
{
int m, n, rb, cb, rd, cd;
cin >> n >> m >> rb >> cb >> rd >> cd;
if (rb <= rd && cb <= cd)
{
cout << max(0,min(rd - rb, cd - cb)) << endl;
continue;
}
else if (rb > rd&& cb<=cd)
{
cout << max(0,min(n - rb + n - rd,cd - cb)) << endl;
continue;
}
else if (cb > cd&&rb<=rd)
{
cout << max(0,min(m - cb + m - cd,rd - rb)) << endl;
continue;
}
else cout << max(0,min(m - cb + m - cd, n - rb + n - rd)) << endl;
}
return 0;
}
第二题
题目: Problem - 1623B - Codeforces
题意:
思维题，Alice有一个集合，开始时集合中只有一个区间[1, n]。Alice每次从集合中拿出一个区间[l, r]，Bob可以在当前区间中挑一个数d，然后Alice将原区间从集合中删除，将符合区间规则的[l, d-1]，[d+1, r]加入集合中，当Bob挑过所有数时，游戏结束。
输入格式
输入包含多组测试用例。
每组测试用例第一行给定一个整数n，然后有n行。每行代表Alice的一个区间。
输出格式
对于Alice的每个区间，给出Bob所挑的数。
可以用任意的排列方式输出结果，因为结果是唯一的。同时两个样例之间不需要有换行，给定的输出样例中的换行是为了方便观察样例。
数据范围
均小于1000
输入样例：
4
1
1 1
3
1 3
2 3
2 2
6
1 1
3 5
4 4
3 6
4 5
1 6
5
1 5
1 2
4 5
2 2
4 4输出样例：
1 1 1
1 3 1
2 2 2
2 3 3
1 1 1
3 5 3
4 4 4
3 6 6
4 5 5
1 6 2
1 5 3
1 2 1
4 5 5
2 2 2
4 4 4思路:
- 水题！（其实是懒不想写=^=，反正这题也挺简单的，有空再写吧~）
代码:
#include<iostream>
#include<string>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int N = 1010;
pair<pair<int,int>, pair<int,int>>p[N];//起点，终点，长度，匹配点
int st[N];
bool cmp1(pair<pair<int, int >, pair<int, int>>a, pair<pair<int, int >, pair<int, int>>b)
{
return a.second.first < b.second.first;
}
int main()
{
int k;
cin >> k;
while (k--)
{
memset(st,0,sizeof st);
int n;
cin >> n;
for (int i = 1; i <= n; ++i)
{
cin >> p[i].first.first >> p[i].first.second;
p[i].second.first = p[i].first.second - p[i].first.first;
}
sort(p + 1, p + n + 1, cmp1);
for (int i = 1; i <= n; ++i)
{
int x = p[i].first.first, y = p[i].first.second;
for (int j = x; j <= y; ++j)
if (!st[j])
{
p[i].second.second = j;
st[j] = 1;
break;
}
}
for (int i = 1; i <= n; ++i)
cout << p[i].first.first << " " << p[i].first.second << " "<< p[i].second.second << endl;
}
return 0;
}
第三题
题目: Problem - 1623C - Codeforces
题意:
有n堆石头，从第三堆石头开始可以往其自身前两堆分石头，同时第二堆分得的石头必须比第一堆少一半。要求我们从头开始分石头，将所有堆中石头数的最小值最大化。
输入格式
输入包含多组测试用例。
每组测试用例第一行是一个整数代表有多少堆石头。第二行是n个整数代表每堆石头初始的石头数量。
输出格式
输出一个整数，表示最大化后的最小值。
数据范围
样例数和石头堆数 1 <= t <= n<= 2e5
每堆的石头数量 1 <= hi <=1e9
输入样例：
4
4
1 2 10 100
4
100 100 100 1
5
5 1 1 1 8
6
1 2 3 4 5 6输出样例：
7
1
1
3思路:
- 让我们通过一次分石头将最小值最大化，那么很显然可以二分寻找目标值。
- 二分判断的条件？既然目标值是最小值，那么它一定满足小于等于所有堆的数量。
- 如何保证二分值是否合法？我们要保证所有的堆一定是大于等于二分值的，那么就必须保证在判断时不能被其它因素干扰，从第三堆开始的石头可以分给前面的石头，所以我们可以从后向前遍历保证在判断每一堆石头时都不会被其它堆影响，然后记录原来堆的值保证不会与从头开始遍历冲突。
- 跟贪心沾边的题目多少都有点反人类…
代码:
#include<iostream>
#include<string>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int N = 200010;
int a[N],b[N],n;
int cherk(int x)
{
for (int i = 1; i <= n; ++i)b[i] = a[i];
//为什么要从后向前遍历？因为我们是在二分区间寻找答案，目标值首先要满足是所有堆中的最小值
//而一个堆的石头数量是可以被后面的堆影响的，我们从后向前遍历可以保证当前堆在检查与二分值的关系时不会被后面的堆影响。
for (int i = n; i >= 3; i--)
{
//因为我们希望将最小值最大化，那么首先要满足就是这个值必须是所有堆的最小值
//所以如果二分值大于当前值说明目标值在左边（也即小的那边），返回0
if (x > b[i])return 0;
else
{
//虽然我们是从后向前遍历，但是有些正向搬运带来的隐性规则要遵守，比如要保证所搬运的石头不能超过该堆的初始值
//其次所能搬运的石头是富余的值，什么是富余的石头，就是在满足当前二分最小值的前提下所能分给前面的堆
int d = min(a[i], b[i]-x) / 3;
b[i] -= d * 3;
b[i - 1] += d;
b[i - 2] += d * 2;
}
}
return b[1] >= x && b[2] >= x ? 1 : 0;
}
int main()
{
int k;
cin >> k;
while (k--)
{
cin >> n;
for (int i = 1; i <= n; ++i)cin >> a[i];//, b[i] = a[i];
int l = 0, r = 1e9;
while (l < r)
{
int mid = (l + r + 1) / 2;
//如果条件满足就说明在右边，否则在左边
if (cherk(mid))l = mid;
else r = mid - 1;
}
cout << l << endl;
}
return 0;
}
