正文
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、、等所有的位置都会延后;
直到所有的数字插入完毕。
因为此处用二分比较简单快捷,就先使用二分。
总结
题目不在乎难易,重点是长期的练习。
有时同事看到我做题,也会纳闷为什么还做算法练习?我说最直接的收益是校招可以出题,社招面试别人也比较有底。还有一句我没说出口,如果以后求职也会用到~
除此之外,就是在脑袋很浆糊的时候,可以整理下思路,特别是在一些非常无聊又不重要的会议上可以做题来打发时间。