正文
题目1
题目链接
题目大意：
在一维坐标轴上有三个点，坐标是a、b、c；
现在需要移动这三个点的位置，使得三个点之间两两间隔大于d；
每次只能移动一个点，每秒只能移动距离1；
问最少需要多少秒，才能满足要求。
输入：
一行，四个数字 𝑎, 𝑏, 𝑐, 𝑑 (1≤𝑎,𝑏,𝑐,𝑑≤10^9)
输出：
最少的秒数。
Examples
input
5 2 6 3
output
2
题目解析：
a、b、c之间没有关系，可以先排序，使得a<b<c。
使得x=b-a, y=c-b，那么有：
x>=d的时候，ans=max(0, d-y);
y>=d的时候，ans=max(0, d-x);
都不满足的时候，ans=(d-x)+(d-y);
int a[3], d, ans = 0;
cin >> a[0] >> a[1] >> a[2] >> d;
sort(a, a + 3);
int x = a[1] - a[0], y = a[2] - a[1];
if (x >= d) {
ans = max(0, d - y);
}
else if (y >= d) {
ans = max(0, d - x);
}
else {
ans = (d - x) + (d - y);
}
cout << ans << endl;
题目2
题目链接
题目大意：
小明用键盘的打字，但是键盘出现故障，每次敲击可能会出现多次结果，比如说按一次h，可能会出现"h"、"hh"、"hhh"等；
现在给出小明打字的原始字符串和目标字符串，问目标字符串是否可能出现？
比如说原始串是"hello"，那么目标串可以为"hello", "hhhhello", "hheeeellllooo"，但不能为"hell", "helo", "hhllllooo"。
输入：
第一行是整数t，表示t个样例；
每个样例有2行输入，第1行是原始字符串，第2行是目标字符串；
输出：
对于每个样例，如果可能出现则输出YES，不可能则输出NO。
Examples
input
5
aa
bb
codeforces
codeforce
polycarp
poolycarpp
aaaa
aaaab
abcdefghijklmnopqrstuvwxyz
zabcdefghijklmnopqrstuvwxyz
output
NO
NO
YES
NO
NO
题目解析：
我们用sourceStr和targetStr来表示原始字符串和目标字符串，根据题目的要求：
1、sourceStr是targetStr的子序列；
2、sourceStr中间某些单词会重复，并且targetStr与sourceStr不同的部分，均由这个重复的单词组成。
基于此，可以从左到右遍历sourceStr和targetStr，用x和y分别来表示sourceStr和targetStr的当前遍历进度；
初始时，x=0, y=0；
如果sourceStr[x]==targetStr[y]，表示同时出现一个字符，那么直接++x和++y；
如果sourceStr[x]!=targetStr[y]，如果是普通字符串匹配，此时会fail，但是这里有题目要求2的特点，targetStr[y]可能是sourceStr[x-1]的重复；所以如果sourceStr[x-1]==targetStr[y]，仍然可以++y，此时x不动；
最后注意把y补齐，判断是否能否x==strlen(sourceStr)，y==strlen(targetStr)，表示是否填充完毕。
int n;
cin >> n;
while (n--) {
string a, b;
cin >> a >> b;
int x = 0, y = 0;
while (x < a.length() && y < b.length()) {
if (a[x] == b[y]) {
++x;
++y;
}
else {
if (x > 0 && b[y] == a[x - 1]) {
++y;
}
else {
break;
}
}
}
while (y < b.length()) {
if (a.back() == b[y]) {
++y;
}
else {
break;
}
}
if (x == a.length() && y == b.length()) {
cout << "YES" << endl;
}
else {
cout << "NO" << endl;
}
}
题目3
题目链接
题目大意：
n个人参加测试，测试需要老师和学生一对一进行，同一时刻只能有一个学生在测试，每个人测试的耗时可能不同；
现在按照1~n的顺序进行测试，已知测试的总时间为m，每个人的测试时间为t[i]；
老师想要知道，对于第i个人，最少需要直接放弃前面多少个人，才能有足够的时间让其能在规定时间m内完成测试；（每个人是相对独立的，对于第i个人和第i+1个人，放弃的人可能各不相同）
输入：
输入共两行
第一行两个整数n and m，分别表示n个人和测试总时间m (1≤n≤100, 1≤m≤100)
第二行是n个整数t[i]，分别表示n个人的测试时间。(1≤𝑡[𝑖]≤100)
输出：
对于每个人，输出通过测试，需要放弃的最少人数；
Examples
input
7 15
1 2 3 4 5 6 7
output
0 0 0 0 0 2 3
样例解释：
对于前5个人，都不需要放弃任何人即可完成测试；
对于第6个人，可以放弃第3、4个人，剩下的人可以完成测试；
对于第7个人，可以放弃第3、4、5个人，剩下的人可以完成测试；
题目解析：
题目的数据范围比较小，可以使用较为粗暴的方式：
记录前i个人的耗时之和sum，如果sum>m，则对前i个人排序，然后从大的开始淘汰，直到sum<=m即可。
int n, m;
cin >> n >> m;
int sum = 0;
for (int i = 0; i < n; ++i) {
cin >> a[i];
sum += a[i];
if (sum <= m) {
ans[i] = 0;
}
else {
sort(a, a + i);
int tmp = sum;
while (tmp > m) {
++ans[i];
tmp -= a[i - ans[i]];
}
}
}
for (int i = 0; i < n; ++i) {
cout << ans[i] << " ";
}
cout << endl;
题目4
题目链接
题目大意：
n个人参加测试，测试需要老师和学生一对一进行，同一时刻只能有一个学生在测试，每个人测试的耗时可能不同；
现在按照1~n的顺序进行测试，已知测试的总时间为m，每个人的测试时间为t[i]；
老师想要知道，对于第i个人，最少需要直接放弃前面多少个人，才能有足够的时间让其能在规定时间m内完成测试；（每个人是相对独立的，对于第i个人和第i+1个人，放弃的人可能各不相同）
输入：
第一行两个整数n and m ，分别表示n个人和测试总时间m (1≤n≤2⋅1e5, 1≤m≤2⋅1e7)
第二行是n个整数t[i]，分别表示n个人的测试时间。(1≤𝑡[𝑖]≤100)
输出：
对于每个人，输出通过测试，需要放弃的最少人数；
Examples
input
7 15
1 2 3 4 5 6 7
output
0 0 0 0 0 2 3
样例解释：
对于前5个人，都不需要放弃人即可完成测试；
对于第6个人，可以放弃第3、4个人，剩下的人可以完成测试；
对于第7个人，可以放弃第3、4、5个人，剩下的人可以完成测试；
题目解析：
相对上一题，这里的数据量更加大。如果再每次排序，复杂度会到达O(N^2logN)的级别。
这里可以用优先队列来进行优化：
维持两个队列，一个是大顶堆top_queue，表示所有已经选中参加考试的人的耗时；
一个是小顶堆tmp_queue，表示所有已经没有被选中参加考试的人的耗时；
从左到右遍历每个人，对于第i个人，如果top_queue中所有人的耗时加上a[i]，仍小于等于m，则答案为tmp_queue的size；
如果top_queue中所有人的耗时加上a[i]大于m，则表示top_queue中的人某些人需要被放弃；
我们从耗时最长的人开始放弃，直到top_queue的总耗时+a[i]<=m，放弃的人都放入tmp_queue，此时答案为tmp_queue的size；
在得到第i个人的耗时之后，将a[i]放入tmp_queue，然后不断从tmp_queue取出最小值x，如果top_queue的总耗时+x<=m，则可以把x放入top_queue。
对于第i个人，top_queue 相当于前i-1个人中，总耗时不大于m的集合，top_queue.top为耗时最长的人；
tmp_queue 表示没被选中人的集合，tmp_queue.top为耗时最短的人；
这个解决理论上是OK的，但是在case13会遇到RunTime Error，比较奇怪；最后查出来是数组越界，但是RE报错在一些完全无关的地方。
fix这个bug之后，顺利通过。
其他思路：
观察题目的数据范围，发现每个人的分数范围是[1, 100]，那么可以用一个人数组来做聚合，避免重复的排序。
a[i] 表示分数为i的人数；
对于第i个人，假设其耗时是k，总耗时不能超过m，那么其他人的耗时是left_time=m-k；
从1~100去遍历分数，对于分数为i的人数有a[i]个；
int t = min(a[j], left_time / j);
cnt += t;
left_time -= t * j;
我们选中了t个分数为i的人。
从小到大遍历一次，相当于我们从分数小的开始选，一直到不能选为止，得到总耗时不超过(m-k)的有cnt个人。
那么答案就是剩下的人。
总结
题目1是简单题，注意a/b/c的大小是随机，但题目样例也给出这种case；
题目2是字符串匹配，细节是x和y匹配到边界的处理，非常容易出错；
题目3是暴力枚举，要发现题目范围小；
题目4是贪心，题目3的基础加大数据范围，可以选择用数据结构来优化处理速度，也可以从题目较小的数据范围入手，更好的针对题目进行优化；
以上题目均来自http://codeforces.com/contest/1185，时间和能力原因只完成了四道题，有兴趣的朋友可以接着去做。
题外话
这是算法练习系列的第四十篇，目标是一百篇。
网友评论