程序员进阶之算法练习(五十三)

时间:2021-7-21 作者:qvyue

正文

题目1

题目链接
题目大意:
有三堆石头,分别有a、b、c个;
现在可以执行操作:
1、从第一堆拿出1个石头,第二堆拿出2个石头;
2、从第二堆拿出1个石头,第三堆拿出2个石头;
以上的操作,必须保证堆中有足够石头才允许操作。

问最多,可以从这三堆石头中拿出多少个。

输入:
第一行,是样例个数 𝑡 (1≤𝑡≤100);
接下来t行表示t个样例,每个样例一行,每行有三个数字a、b、c (0≤𝑎,𝑏,𝑐≤100);

输出:
每个样例一行,输出拿到的石头数量。

input
3
3 4 5
1 0 5
5 3 2

output
9
0
6

题目解析:
由题目的条件可以知道,操作1和操作2都会依赖第二堆的石头,所以第二堆石头的分配就成为了关键;
为了高效利用第二堆石头,我们优先执行操作2,再执行操作1。

int main(int argc, const char * argv[]) {
    int a, b, c;
    int t;
    cin >> t;
    while (t--) {
        cin >> a >> b >> c;
        int ans = min(c / 2, b);
        cout 

题目 2

题目链接
题目大意:
给出两个整数l和r,已知l
现在希望找到一个整数x,要求是 l
如果能找到则输出这个数字;
如果不能找到则输出-1;

输入:
两个整数l和r; (1≤𝑙≤𝑟≤1e5)

输出:
输出整数x;如果不存在则输出-1;

题目解析:
直接遍历整数区间的数字,判断每个数字是否合法。

扩展思考题🤔:假如题目的数据范围非常大,甚至没有限制呢?在无法枚举的情况下,求出一个最小的解。

int main(int argc, const char * argv[]) {
    int x, y;
    cin >> x >> y;
    while (x 

题目3

题目链接
题目大意:
有n个整数,𝑎1,𝑎2,…,𝑎𝑛;
可以去掉中间某一段连续的数字,要求剩下的数字没有重复。
问,最少需要去掉多少个数字。

输入:
第一行,整数𝑛 (1≤𝑛≤2000)
第二行,n个整数𝑎1,𝑎2,…,𝑎𝑛 (1≤𝑎𝑖≤1e9)

输出:
最少需要去掉数字个数

Examples
input
3
1 2 3
output
0
input
4
1 1 2 2
output
2

题目解析:
不考虑复杂度,直接枚举去掉区间的坐标[l, r],有n^2的可能;
判断剩下数字有没有重复需要O(N)的时间,总的时间复杂度是O^3,超过了可接受范围;

假如去掉x个数字有解,则去掉x+1个数字也有解,可以用2分来优化;
这样复杂度可以优化为O(NNlogN),可接受范围内。

提交错误(TLE)1次,数字较大且map耗时较多;改为scanf,添加hash处理,可以满足要求。

    map h;
    for (int i = 0; i 

更优化的做法:
假设去掉的数字区间是[l, r],那么剩下的就是[0, l-1]和[r+1, n-1]的区间。
容易知道[0, l-1]和[r+1, n-1]里面是没有重复元素的。
从0开始遍历,可以很容易得到以0为起点的不重复元素区间;
同理,从n-1开始向左遍历,可以得到以n-1为结束的不重复元素区间;
以上两步的处理都是O(N)复杂度。

假设得到左边最大的不重复元素区间,也得到右边最大不重复元素区间;
那么就可以枚举左边区间长度(从长度为0开始),对于[0, k)的区间,求出[0, k)中所有元素的最右边距离difMax,那么从difMax+1开始,右边的元素就不会再和左边的[0, k)相同,这样再和右边最大不重复元素区间取一个较小值。

可以O(N)解决这个问题。

提交错误(WA)1次,少考虑了左边完全不需要的情况,ans的初始化有误,比如说:
8
1 1 1 1 5 6 7 1
这样的样例会返回7,因为默认了第一个1数字会选择,实际上还有一种情况是左边数字1区间不取。


int a[N];
int vis[N];
int cnt = 0;
// [l, r)
bool check(int n, int l, int r) {
    memset(vis, 0, sizeof(vis));
    for (int i = 0; i > n;
    
    map leftMap, rightMap, gapMap;
    for (int i = 0; i = 0; --i) {
        if (rightMap[a[i]]) {
            break;
        }
        rightMap[a[i]] = 1;
        rightDifMax = i;
    }
    
    int tmp = 0, ans = (n - rightDifMax);
    for (int i = 0; i 

题目4

题目链接
题目大意:
给出n个数字,每次可以选择若干个数字,将他们进行平均;(如果不能整除,会用分数来表示)
这个操作的次数不限制;

问最终最多有多少个数字可以大于x?

输入:
第一行,整数𝑡表示有t个样例数量 (1≤𝑡≤1000)
每个样例第一行, 整数𝑛 and 𝑥 (1≤𝑛≤10^5, 1≤𝑥≤10^9)
接下来一行n个整数𝑎1,𝑎2,…,𝑎𝑛 (1≤𝑎𝑖≤10^9)

输出:
每个样例一行,最终大于数字x的数量;

Examples
input
4
4 3
5 1 2 1
4 10
11 9 11 9
2 5
4 3
3 7
9 4 9

⁣output
⁣2
4
0
3

题目解析:
把数字从大到小排序,从数字大的开始选择:
1、如果该数字大于x,直接入选;
2、如果该数字小于x,并且加进来不会导致sum/count 小于x,则加进来;

直到数字不能选择,则得到最多的数字。

int main(int argc, const char * argv[]) {
    // insert code here...
    
    int t;
    cin >> t;
    while (t--) {
        lld n, x;
        cin >> n >> x;
        
        for (int i = 0; i = 0; --i) {
            if (sum + a[i] >= x * (ans + 1)) {
                sum += a[i];
                ++ans;
            }
            else {
                break;
            }
        }
        cout 

题目5

题目链接
题目大意:
小明在打游戏,有n只怪物围绕成一圈,第1只和第n只相邻;
第i只怪物的血量为a[i],小明每次可以攻击一只怪物,使得怪物的血量-1;
当怪物的血量小于等于0的时候会死亡,并且产生爆炸,对第i+1个位置的怪物造成b[i]点伤害;(如果是第n只怪物爆炸,则是对第1只怪物造出伤害)
现在想知道,小明最少攻击多少次,才能使得所有怪物都爆炸;

输入:
第一行,整数𝑡表示有t个样例数量 (1≤𝑡≤1000)
每个样例第一行, 整数𝑛 (2≤𝑛≤300000)
接下来n行,每行两个整数𝑎𝑖 and 𝑏𝑖 (1≤𝑎𝑖,𝑏𝑖≤1e12)

输出:
每个样例一行,小明的最少攻击次数。

Examples
input
1
3
7 15
2 14
5 3
⁣output
⁣6

题目解析:
题目有两个点使得决策比较复杂:1、n个怪物绕成一个圈;2、怪物死亡之后,会产生爆炸;
先不考虑怪物死亡后爆炸的问题,就是n只怪物的血量和;
再考虑爆炸的情况,由于题目要求的是最终所有怪物都死亡,即所有怪物都会爆炸,那么可以直接减去爆炸影响的血量;

接下来的问题是,找到n个怪物中,应该首先攻击哪一个,使得其最先爆炸;
这个可以先统计一遍所有怪物减去被爆炸影响后的血量和,然后遍历每一个怪物,枚举这个怪物如果最先爆炸,最终的攻击次数。


int main(int argc, const char * argv[]) {
    // insert code here...
    
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        
        for (int i = 0; i 

思考🤔:
如果是双向爆炸呢?
即位置i有多种可能爆炸顺序, i最先爆炸,i-1先爆炸然后i爆炸,i+1先爆炸然后i爆炸,i-1和i+1都爆炸然后i再爆炸;
这样需要考虑复杂很多!

总结

题目1 简单贪心,因为两个操作的控制要素不多,比较容易抉择;
题目2 简单模拟,题目的要求和范围都很简单,但是扩展题目的需要一点思路+代码能力;
题目3 暴力计算,枚举区间的做法比较暴力,收获也比较少,优化做法会更佳;
题目4 排序选择,排序简化思考,核心把平均数用和表达出来;
题目5 简化思考,部分决策因素会导致题目很复杂,从结果反推,配合枚举是很好的方式。

声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎发送邮件至:qvyue@qq.com 进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。