正文
题目1
题目链接
题目大意：
给出n个整数，还有一个数字d；
要求去除最少的数字，使得剩余数字的最大最小值差不大于d；
输入数据：
n and d (1 ≤ n ≤ 100, 0 ≤ d ≤ 100)
(1 ≤ x[i] ≤ 100)
Examples
input
3 1
2 1 4
output
1
题目解析：
方法1：
贪心。假设最后的结果是区间是[left, right]，那么小于left、大于right的数字全部要抛弃。
先对数组排序，假设数字a[i]是left，那么通过二分查找right=a[i]+d，可以快速算出应该要抛弃的数字。
方法2：
暴力。先排序，枚举保留的数据区间[left, right]，计算是否满足最大最小值差小于d。
方法3：
扫描线。先排序，从左到右扫描，保持一个最大最小值差小于d的区间；如果区间不满足，则从区间左边抛弃元素。
int a[N];
int main(int argc, const char * argv[]) {
// insert code here...
int n, d;
cin >> n >> d;
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
sort(a, a + n);
int ans = n;
for (int i = 0; i < n; ++i) {
int right = upper_bound(a, a + n, a[i] + d) - a;
ans = min(ans, i + n - right);
}
cout << ans << endl;
return 0;
}
题目2
题目链接
题目大意：
给出四个整数n，k，A，B;
现在需要把数字n变成数字1，每次有两个操作：
1、n=n-1, 代价为A；
2、n=n/k，代价为B；（要求是n能被k整除）
求最小代价。
输入数据：
四行整数，分别表示 n、k、A、B (1 ≤ n,k,A,B ≤ 2·1e9)
Examples
input
9
2
3
1
output
6
样例解释：
Subtract 1 from x (9 → 8) paying 3 coins.
Divide x by 2 (8 → 4) paying 1 coin.
Divide x by 2 (4 → 2) paying 1 coin.
Divide x by 2 (2 → 1) paying 1 coin.
题目解析：
直接的做法，每次判断操作的代价，选择最小的代价进行操作，直到数字变为1。
但是因为n的数字较大，如果出现极端的情况，可能会进行n-1次操作1，这样使得复杂度过高。
换一种思路，操作2只能发生在n%k==0的情况，那么只需判读数字n变成n/kk的操作代价是否划算。
假设t=n/kk，那么如果数字t进行操作2都不划算，那么往后所有的操作2都是不划算的。
思考🤔：
代码很简洁。
int main(int argc, const char * argv[]) {
lld n, k, a, b;
cin >> n >> k >> a >> b;
lld ans = (n - 1) * a;
while (n > 1) {
lld t = n / k * k;
if ((t - t / k) * a <= b) {
break;
}
else {
n = t / k;
ans = ans - (t - t / k) * a + b;
}
}
cout << ans << endl;
return 0;
}
题目3
题目链接
题目大意：
给出一个长度为n的字符串str，字符串由小写字母拼成；
现需要拼一个新字符串，要求：
1、长度为k，全部为小写字母，且字母都在str中出现过；
2、新字符串的字典序大于str，且尽可能小；
输入数据：
第一行 n and k (1 ≤ n, k ≤ 100 000)
第二行 字符串str
Examples
input
3 3
abc
output
aca
样例解释：
aaa, aab, aac, aba, abb, abc, aca, acb, .... 都是满足条件1；
其中字典序大于abc，且尽可能小的是aca；
题目解析：
题目分俩种情况讨论：
1、k > n，那么只需要用str中最小的字符填满(strNew-str)后面的字符；
2、k <= n，从右往左遍历，寻找某一位i，strNew[i]>str[i]，之后的字符全部用str中最小的字符填满。
思考🤔：
也可以借用模拟加法的方式来思考，比如说abc的下一个字符串是abc+a=abd，d进位变成aca。
char str[N];
int vis[3333];
int main(int argc, const char * argv[]) {
int n, k;
cin >> n >> k;
cin >> str;
for (int i = 0; i < n; ++i) {
vis[str[i]] = 1;
}
if (k > n) {
cout << str;
for (int i = 0; i < 26; ++i) {
int index = 'a' + i;
if (vis[index]) {
for (int j = 0; j + n < k; ++j) {
putchar(index);
}
break;
}
}
cout << endl;
}
else {
for (int i = k - 1; i >= 0; --i) {
int bigger = 0;
for (int j = str[i] + 1; j < 'a' + 26; ++j) {
if (vis[j]) {
bigger = j;
break;
}
}
if (bigger) {
str[i] = bigger;
for (int j = 0; j < 26; ++j) {
int index = 'a' + j;
if (vis[index]) {
for (int t = i + 1; t < k; ++t) {
str[t] = index;
}
break;
}
}
break;
}
}
str[k] = 0;
cout << str << endl;
}
return 0;
}
题目4
题目链接
题目大意：
我们用一个字符串来描述一串项链，字符串由'o'和'-'组成，o表示珠子，-表示链条；（字符串第一个字符和最后一个字符相连）
现在可以对项链进行重新组合，即对'o' '-'的字符串重新排列，问是否能满足要求：
珠子之间链条的数量是相同；
输入：
第一行：字符串str，表示项链；（注意，可能出现一个珠子、多个珠子、没有珠子的情况）
输出：
YES如果能满足要求，NO如果不能满足要求；
输入数据：
Examples
input
-o-o--
output
YES
题目解析：
先统计-和o的数量x，y；
分类讨论：
y=0的时候，那么必然是YES；
y!=0，那么当x%y==0的时候，是YES；否则是NO；
int main(int argc, const char * argv[]) {
string str;
cin >> str;
int x = 0, y = 0;
for (int i = 0; i < str.length(); ++i) {
if (str[i] == '-') {
++x;
}
else {
++y;
}
}
if (y == 0 || x % y == 0) {
cout << "YES" << endl;
}
else {
cout << "NO" << endl;
}
return 0;
}
题目5
题目链接
题目大意：
小明正在上图像算法课程，老师要求他实现一个图像滤镜算法，其处理过程可以这么描述：
给出n个数字p[i]，[0, 255]范围，表示颜色；
把范围[0, 255]划分多个区间比如说[0, 4], [5, 9], [10, 14]....要求区间的大小不超过k；（注意区间要求是连续的，区间数量没有要求，区间的长度有限制）
然后对数据进行处理，区间[0, 4]内的数字都可以用0表示，同理[5, 9]=5；
要求处理之后所有的数字形成的字典序最小。
输入：
第一行 n，k ( 1 ≤ n ≤ 1e5 , 1 ≤ k ≤ 256 )
第二行 p 1 , p 2 , … , p n ( 0 ≤ p i ≤ 255 )
输出：
处理字后的n个数字。
Examples
input
4 3
2 14 3 4
output
0 12 3 3
样例解释
color 2 属于 group [0, 2] = 0
color 14 = group [12, 14] = 12
color 3,4 = group [3, 5] = 3
所以最终数字是0，12，3，3
题目解析：
所有的数字形成的字典序最小，相当于前面的数字越小越好。
那么在考虑第i个数字的时候，可以不管i+1之后的数据，尽可能满足第i个数字最小。
由此，我们可以得到一个贪心策略：
默认[0, 255]都不分配区间，对第i个数字，其颜色值p[i]，我们从p[i]-1开始往前找还没分配的区间，这时会有两种情况：
1、都没有分配，那么我们可以把(p[i] - k + 1, p[i])分配成一个区间；
2、找到一个已经分配的区间（x, y），那么看这个区间的长度是否能达到（x, p[i]），如果可以则把区间放大成(x, p[i]);
如果长度不够，那么则从(y + 1, p[i]）分配一个区间；
这样可以得到一个最小字典序。
int main(int argc, const char * argv[]) {
int n, k;
cin >> n >> k;
int cnt = 1;
for (int index = 0; index < n; ++index) {
int x;
cin >> x;
if (!color[x]) {
int cur, ok = 0;
for (cur = x - 1; cur >= 0 && cur + k > x; --cur) {
if (color[cur]) {
int len = checkLen(cur);
if (len + (x - cur) <= k) {
ok = color[cur];
}
break;
}
}
if (ok) {
while (cur <= x) {
color[cur++] = ok;
};
}
else {
while (cur < x) {
++cur;
color[cur] = cnt;
}
cnt++;
}
}
cout << x - checkLen(x) + 1 << " ";
}
return 0;
}
总结
题目1，题目要求简单，但是有很多种做法；
题目2，贪心的思路，决策的关键节点在能整除的时候；
题目3，模拟加法，用分类讨论的思路也很清晰；
题目4，分类讨论，环是模拟起来比较费脑的东西，可以画图思考；
题目5，贪心，尽可能让前面的数字更小。
