正文
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
题目解析：
直观的想法，是保留最高的一列（这样右视图不变），然后每列只保留一个格子，保证上视图不变。
但是这样不是最优解，比如说样例：
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
样例解释：
题目解析：
尝试构造一种最优解：
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、、等所有的位置都会延后；
直到所有的数字插入完毕。
因为此处用二分比较简单快捷，就先使用二分。
总结
题目不在乎难易，重点是长期的练习。
有时同事看到我做题，也会纳闷为什么还做算法练习？我说最直接的收益是校招可以出题，社招面试别人也比较有底。还有一句我没说出口，如果以后求职也会用到~
除此之外，就是在脑袋很浆糊的时候，可以整理下思路，特别是在一些非常无聊又不重要的会议上可以做题来打发时间。
