程序员进阶之算法练习（五十四）
正文
题目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，贪心，尽可能让前面的数字更小。