程序员进阶之算法练习（三十七）Codeforces
正文
1、Coins
题目链接 题目大意： 假设有面值为1、2、3、、、n元的硬币，每种硬币都有无限个，要凑出S元，最少需要多少个硬币？
输入： 一行，两个整数? and ? (1≤?≤100000, 1≤?≤1e9)
输出： 最少的硬币数量。
Examples input 5 11 output 3 input 6 16 output 3
题目解析： 因为每种硬币无限多，那么可以直接先取面值最大的硬币，剩下的额度再用对应的硬币即可。
int n, s;
cin >> n >> s;
int ans = s / n;
if (s % n) {
++ans;
}
cout << ans;思考?： 如果硬币面值是1、5、7呢？
2、Views Matter
题目链接 题目大意： 在n*m的网格中，每一列网格有一个高度a[i]，表示这一列网格的底部会有a[i]个方块。 如下，这个图表示在4*4的网格中，分别有[2,1,3,1]个方块。
现在假设从上面和从右边去看这个网格，会生成两个视图。 希望拿掉尽可能多的方块，但是上视图和右视图保持不变。
输入： 第一行， ? and ? (1≤?≤100000, 1≤?≤1e9) 第二行，n个数字?1,?2,…,?? (1≤??≤?)
输出： 一个数字，最大的可移除方块数量。
Examples input 5 6 3 3 3 3 3 output 10 input 3 5 1 2 4 output 3
样例解释，蓝色为可移除数量，共10个
题目解析： 直观的想法，是保留最高的一列（这样右视图不变），然后每列只保留一个格子，保证上视图不变。 但是这样不是最优解，比如说样例： 00x 0xx xxx 按照上述的逻辑，保留最右边的一列，然后每列留一个，于是只能去掉中间列底部的x； 但实际上，第三列的下面两个格子，也是处于可以去掉的部分。
对原来的思路进行优化，先保留最高的一列，对于每一列保留一个顶部的格子，并记录对应格子的高度h[i]；
最后再针对格子的高度数组h[i]，从最高的列中计算有哪些格子可以去掉； 为了方便计算，先对结果排个序。
int n, m;
cin >> n >> m;
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
sort(a, a + n);
lld sum = 0, ans = 0;
for (int i = 0; i < n - 1; ++i) {
if (sum < a[i]) {
++sum;
}
if (a[i]) {
ans += a[i] - 1;
}
}
if (n >= 2 && sum >= a[n - 1]) {
--sum;
}
cout << ans + sum << endl;3、Nauuo and Votes
题目链接 题目大意： 小明在某个社区进行评论，有x个人点赞同，y个人点反对，z个人可能会点赞同，也可以会点反对； 如果赞同人数大于反对人数，则小明的评论旁边会显示"+"； 如果反对人数大于赞同人数，则小明的评论旁边会显示"-"； 如果反对人数等于赞同人数，则小明的评论旁边会显示"0"； 问，小明这个评论旁边可能会显示什么？
输入： 一行，?, ?, ? (0≤?,?,?≤100)
输出： 如果结果是确定的，则输出"+"、"-"、"0"； 如果结果不确定，则输出"?";
Examples input 2 0 1 output + input 2 2 2 output ?
题目解析： dif=abs(x-y)； 如果dif>z，则直接输出+/-； 如果dif<z，则直接输出?； 如果dif==z，则看z是否为0，不为0则输出?，为0则输出0；
int x, y, z;
cin >> x >> y >> z;
int dif = x > y ? x-y : y-x;
if (dif > z) {
cout << (x > y ? "+" : "-") << endl;
}
else if (dif < z) {
cout << "?" << endl;
}
else {
if (z == 0) {
cout << 0 << endl;
}
else {
cout << "?" << endl;
}
}4、Nauuo and Chess
题目链接 题目大意： 在一个 m x m 的棋盘上，要放置n个棋子。 假设第i个棋子放置在??行，??列，那么要满足以下条件： 对于所有的i、j，都有 |??−??|+|??−??|≥|?−?| 。
问，m的最小值是多少？
输入： 一行，数字? (1≤?≤1000)，表示棋子数量。
输出： 第一行是数字m，表示棋盘大小； 接下来有n行，每行两个数字?? and ?? (1≤??,??≤?），分别表示第i个棋子放置的行数和列数。
Examples input 2 output 2 1 1 1 2 input 4 output 3 1 1 1 3 3 1 3 3 样例解释：
样例1，m=2的放置方式
样例2，m=3的放置方式
题目解析： 尝试构造一种最优解： 123 004 005
1234 0005 0006 0007
因为相对1而言，往右、往下都存在(x,y)坐标的递增； 从上面可以知道，这种填充方式已经是最优解。 比如说当我们往6的左边填入一个数字时，因为6相对1已经是距离最大值，而向左填入会导致y坐标减1，那么填入的数字只能比6更小。
代码非常简洁：
int n, m;
cin >> n;
m = n / 2 + 1;
cout << m << endl;
int index = 0;
while (n && index < m) {
--n;
++index;
cout << "1 " << index << endl;
}
index = 1;
while (n && index < m) {
--n;
++index;
cout << index << " " << m << endl;
}思考： 如何得到这个最优解？ 还是贪心的原则，1是最小，放在最边上肯定没错； 2贴着1放，也是最优解； 同理，3也要贴着2进行放置； ...
5、Nauuo and Cards
题目链接 题目大意： 小明有 2 x n 张卡片，其中n张卡片序号是1、2、3、、、n，另外n张的卡片序号是0。 现在这些卡片都随机打乱，分成2组卡片，从上到下分别为a[i]和b[i]。 现在小明在玩一个游戏，卡片a组是手牌，卡片b组是目标卡组。 每次小明可以从手牌中拿出一张卡片（可以是手牌中任意一张），放置在卡片b组的最下面，然后从卡片b组中的最上面拿掉一张卡片放入手牌。 小明希望用这个操作，使得目标卡组从上到下分别为1、2、3、4、、、、n。 问，最少需要多少次操作。
输入： 第一行，数字? (1≤?≤2⋅105) 第二行，n个数字表示a[i]，?1,?2,…,?? (0≤??≤?) 第三行，n个数字表示b[i]，?1,?2,…,?? (0≤??≤?)
输出： 一个数字，最少的次数。
Examples input 3 0 2 0 3 0 1 output 2 input 3 0 2 0 1 0 3 output 4 input 11 0 0 0 5 0 0 0 4 0 0 11 9 2 6 0 8 1 7 0 3 0 10 output 18
题目解析： 小明手上的n张卡片a[n]，另外的n张卡片是b[n]; 最终的结果数组a全部是0，数组b=1,2,3...,n;
先不考虑复杂度，可以把b中所有的非零数字先用0换取出来； 然后按照顺序放入1~n个数字，可以用最多2*n次操作完成。
简化这个思考逻辑，我们发现这个操作其实就是队列的操作。
3 0 2 0 3 0 1 那么这里的交换其实就是: [3,0,1,2,3] 原始是[3,0,1]，第一次操作后是[0,1,2]，第二次操作之后是[1,2,3]，满足要求；
3 0 2 0 1 0 3 [1,0,3,0,1,2,3] 是第二样例；
总结前面的思路，就是不断拿0去交换b里面的数字，直到a里面的数字可以开始填1、2、3...； 现在的问题是如何断定1开始填是可以的？
容易知道如果从第x个位置开始填入有解，那么从第x+1个位置开始填也是有解。 那么可以从[1, n]二分，最终得到一个有效的解。
这里需要考虑一种特殊情况，就是填充的数字不是从1开始的。
如果不想用二分呢？ 有解决方案！ 从左到右遍历数组b，对于每个位置都判断一次： 当前的数字是x（x从1开始），如果x在手牌中，则使用x，然后获得该位置对应的卡片；（x+1） 如果当前的数字x没有在手牌上，则可以在原来最开始的位置先插入0，延后1的插入位置，那么2、3、4、、等所有的位置都会延后； 直到所有的数字插入完毕。
因为此处用二分比较简单快捷，就先使用二分。
总结
题目不在乎难易，重点是长期的练习。 有时同事看到我做题，也会纳闷为什么还做算法练习？我说最直接的收益是校招可以出题，社招面试别人也比较有底。还有一句我没说出口，如果以后求职也会用到~ 除此之外，就是在脑袋很浆糊的时候，可以整理下思路，特别是在一些非常无聊又不重要的会议上可以做题来打发时间。