专栏首页落影的专栏程序员进阶之算法练习(五十三)

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

正文

题目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 << min((b - ans) / 2, a) * 3 + ans * 3 << endl;
    }
    return 0;
}

题目 2

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

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

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

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

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

int main(int argc, const char * argv[]) {
    int x, y;
    cin >> x >> y;
    while (x <= y) {
        int ok = 1;
        int a[10] = {0};
        int tmp = x;
        while (tmp) {
            if (a[tmp % 10]) ok = 0;
            a[tmp%10] = 1;
            tmp /= 10;
        }
        if (ok) {
            cout << x << endl;
            return 0;
        }
        ++x;
    }
    cout << -1 << endl;
    
    return 0;
}

题目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<int, int> h;
    for (int i = 0; i < n; ++i) {
        int t;
        scanf("%d", &t);
        if (!h[t]) {
            h[t] = ++cnt;
        }
        a[i] = h[t];
    }

    int left = 0, right = n; // [left, right)
    int ans = n - 1;
    while (left < right) {
        int mid = (left + right) / 2;
        int ok = 0;
        for (int k = 0; k < n; ++k) { //
            if (check(n, k, k + mid)) {
                ok = 1;
                break;
            }
        }
        if (ok) {
            ans = mid;
            right = mid;
        }
        else {
            left = mid + 1;
        }
    }
    cout << ans << endl;

更优化的做法: 假设去掉的数字区间是[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 < l; ++i) {
        if (!vis[a[i]]) {
            vis[a[i]] = 1;
        }
        else {
            return false;
        }
    }
    for (int i = r; i < n; ++i) {
        if (!vis[a[i]]) {
            vis[a[i]] = 1;
        }
        else {
            return false;
        }
    }
    return true;
}

int main(int argc, const char * argv[]) {
    // insert code here...
    int n;
    cin >> n;
    
    map<int, int> leftMap, rightMap, gapMap;
    for (int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
        gapMap[a[i]] = i;
    }
    
    int leftDifMax = 0, rightDifMax = 0;
    for (int i = 0; i < n; ++i) {
        if (leftMap[a[i]]) {
            break;
        }
        leftMap[a[i]] = 1;
        leftDifMax = i;
    }
    
    for (int i = n - 1; 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 <= leftDifMax; ++i) {
        tmp = max(tmp, gapMap[a[i]]);
        int r = max(rightDifMax, tmp + 1);
        ans = max(ans, i + 1 + (n - r));
    }
    
    cout << (n - ans) << endl;
       
    return 0;
}

题目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 < n; ++i) {
            scanf("%d", &a[i]);
        }
        sort(a, a + n);
        lld sum = 0, ans = 0;
        for (int i = n - 1; i >= 0; --i) {
            if (sum + a[i] >= x * (ans + 1)) {
                sum += a[i];
                ++ans;
            }
            else {
                break;
            }
        }
        cout << ans << endl;
    }
    
    return 0;
}

题目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 < n; ++i) {
            scanf("%lld%lld", &a[i], &val[i]);
        }
        
        lld sum = max(0ll, a[0] - val[n - 1]);
        for (int i = 1; i < n; ++i) {
            sum = sum + max(0ll, a[i] - val[i - 1]);
        }
        
        lld ans = sum - max(0ll, a[0] - val[n - 1]) + a[0]; // 直接打死第0个
        for (int i = 1; i < n; ++i) {
            lld tmp = sum - max(0ll, a[i] - val[i - 1]) + a[i];
            ans = min(ans, tmp);
        }

        cout << ans << endl;
    }   
    
    return 0;
}

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

总结

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 程序员进阶之算法练习(三十五)LeetCode专场

    LeetCode上的题目是大公司面试常见的算法题,今天的目标是拿下5道算法题: 题目1是基于链表的大数加法,既考察基本数据结构的了解,又考察在处理加法过程中的...

    落影
  • 程序员进阶之算法练习(三十五)LeetCode专场

    LeetCode上的题目是大公司面试常见的算法题,今天的目标是拿下5道算法题: 题目1是基于链表的大数加法,既考察基本数据结构的了解,又考察在处理加法过程中的边...

    落影
  • 程序员进阶之算法练习(十五)

    前言 有朋友推荐一个新的算法练习网站leetcode,说北美的公司招人都是400题起步,国内公司招聘也经常用到,上海的尤其多。 很有意思,可以花点时间做做le...

    落影
  • 程序员进阶之算法练习(十三)

    前言 比赛就在这周末,这篇是比赛前最后一篇训练总结。 正文 hdu 5980(简单题) 题目大意 一个32位的数字,每个bytes包括8bit,所以一个整...

    落影
  • 程序员进阶之算法练习(二十五)

    前言 算法题是锻炼思维的好工具,在解决问题的层面考察思考能力。 正文 1. Compote 题目链接 题目大意: 给出a、b、c三种材料,可以1:2:4组成...

    落影
  • 程序员进阶之算法练习(四十五)

    每个路口的机动车道有三个方向,分别是左转、直行、右转,同时路口有一条人行道; 每行输入有四个数字l,s,r,p,分别表示左转、直行、右转、人行道的交通信号灯是...

    落影
  • 程序员进阶之算法练习(五十二)

    题目链接 题目大意: n个人参加比赛,每个人都有一个分数a[i],现在需要给这些人发奖牌(每个人最多发一个),要求:

    落影
  • 程序员进阶之算法练习(五十一)

    输入: 第一行,整数?表示有t个样例数量 (1≤?≤1000) 接下来每个样例一行,整数? (1≤?≤10^9).

    落影
  • 程序员进阶之算法练习(三十一)

    BAT常见的算法面试题解析: 程序员算法基础——动态规划 程序员算法基础——贪心算法 工作闲暇也会有在线分享,算法基础教程----腾讯课堂地址。

    落影

扫码关注云+社区

领取腾讯云代金券