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

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

正文

题目1. Sagheer and Crossroads

题目链接 题目大意: 在一个十字路口(见图),一共有4个路口;

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

如果某个路口人行道的灯亮起,同时有机动车可以通过这个路口,那么会发生交通事故,输出"YES"; 如果所有的路口都不会发生交通事故,则输出"NO";

Examples input 1 0 0 1 0 1 0 0 0 0 1 0 0 0 0 1 output YES 样例解释: 路口1的人行道信号灯亮起的同时,路口1和4的机动车可以通过这个路口,会发生交通事故; 同时路口4的人行道信号灯亮起的同时,路口2、3的机动车可以通过路口4,会发生交通事故;

题目解析: 题意很清晰,分别判断每个路口是否有人行道信号灯亮起,如果有再判断是否有机动车通过。

    int n = 4;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            cin >> a[i][j];
        }
    }
    
    for (int i = 1; i <= n; ++i) {
        if (a[i][4] == 1) { // pedestrian light on
            int l = i > 1 ? i - 1 : 4, r = i < 4 ? i + 1 : 1, s = i + 2 > 4 ? (i + 2) % 4 : i + 2;
            if (a[l][3] || a[r][1] || a[s][2] || a[i][1] || a[i][2] || a[i][3]) {
                cout << "YES" << endl;
                return 0;
            }
        }
    }
    
    cout << "NO" << endl;

题目2.Sagheer, the Hausmeister

题目链接 题目大意: 在一栋大厦里,有n层,每层有m个房间,同时每层的左右两侧都存在一个楼梯; 有些人晚上离开大厦没有关灯,小明是大厦的管理员,每天晚上需要把所有的房间的灯关掉; 输入n行数据,每行有m+2个数字,第一列和最后一列表示楼梯,第2列到第m+1列表示房间的灯(1表示亮着); 小明一开始在最底层(第n行)左边的楼梯的位置,假设小明上一层楼梯的时间为1,经过一个房间的时间也为1,关灯的不耗费时间; 并且小明会把这一行的灯都关掉,再走到上一层。

问,小明最少需要多少时间,才能关掉所有的灯;

Example input 3 4 001000 000010 000010 output 12

题目解析: 典型的动态规划。 每一层的初始状态只有两种:最左或者最右。 走到上一层的时候,也只有最左和左右两个选择。 那么,一共有4种情况: 1、初始在最左,走完当前层,然后回到最左; 2、初始在最左,走完当前层,然后直接到最左; 3、初始在最右,走完当前层,然后回到最右; 4、初始在最右,走完当前层,然后直接到最左; 这也是四个状态转移方程。 第i层,我们用lMax[i]和rMax[i]来表示,这一层灯的最左边和最右边位置,这样可以快速算出走完当前层的代价。 详细代码转移见下面:(trick,可能某一层为全部为0)

   int n, m;
   cin >> n >> m;
   for (int i = 1; i <= n; ++i) {
       cin >> a[i];
       for (int j = 1; j <= m; ++j) {
           if (a[i][j] == '1') {
               rMax[i] = j;
           }
       }
       for (int j = m; j >= 1; --j) {
           if (a[i][j] == '1') {
               lMax[i] = m - j + 1;
           }
       }
   }
   
   dp[n + 1][0] = -1, dp[n + 1][1] = inf;
   for (int i = n; i >= 1; --i) {
       int upStep = 1;
       // 1 从右到左,从左到左
       dp[i][0] = dp[i + 1][1] + upStep + (m + 1);
       dp[i][0] = min(dp[i][0], dp[i + 1][0] + upStep + rMax[i] * 2);
       
       //
       dp[i][1] = dp[i + 1][0] + upStep + (m + 1);
       dp[i][1] = min(dp[i][1], dp[i + 1][1] + upStep + lMax[i] * 2);
   }
   
   int cur = 1;
   while (cur < n && lMax[cur] == 0) { // 找到最后一层有灯的
       ++cur;
   }
   
   cout << min(dp[cur + 1][0] + rMax[cur] + 1, dp[cur + 1][1] + lMax[cur] + 1) << endl;

题目3.Sagheer and Nubian Market

题目链接 题目大意: 小明到商店买东西,商店里有n个物品,小明带了总共s的钱; 每个商品有个基础的价格a[i],同时商品还有一个附加价格: 当小明总共购买k个物品的时候,每个商品的价格=基础价格+附加价格=a[i]+i*k

现在小明希望在总价格不超过s的前提下,尽可能买更多的物品; 如果物品一样多,小明希望总价格price尽可能的少;

输入数据 n and s (1 ≤ n ≤ 1e5 and 1 ≤ s ≤ 1e9) (1 ≤ ai ≤ 1e5) 输出数据 能买到物品数量和总价格price;

Examples input 3 11 2 3 5 output 2 11

样例解释: 样例中,小明无法购买3个物品,因为购买3个时,价格是 [5, 9, 14],总价格是28; 如果购买2个物品,价格是 [4, 7, 11],小明可以买前两个。

题目解析: 在不考虑附加价格的时候,可以直接对价格排序,从价格最小的物品开始,直到无法购买即可; 附加价格的影响是当购买的物品越多的时候,物品的的价格是越贵,这里是具有单调性的。 那么通过二分购买的数量mid,即可排除附加价格的影响。 每次得到二分的购买数量mid后,更新每个物品的价格,再排序进行求值。 总得复杂度是二分复杂度*排序复杂度=O(NlogNlogN);

    lld n, s;
    cin >> n >> s;
    for (int i = 1; i <= n; ++i) {
        scanf("%lld", &node[i]);
    }
    
    lld l = 0, r = n + 1, ans = 0, ansTotal = 0;
    while (l < r) {
        lld mid = (l + r) / 2;
        if (mid == 0) {
            break;
        }
        lld sum = 0;
        for (int i = 1; i <= n; ++i) {
            a[i] = node[i] + mid * i;
        }
        sort(a + 1, a + 1 + n);
        for (int i = 1; i <= mid; ++i) {
            sum += a[i];
        }
        if (sum > s) {
            r = mid;
        }
        else {
            ans = mid;
            ansTotal = sum;
            l = mid + 1;
        }
    }
    cout << ans << " " << ansTotal << endl;

题目4. Game of Credit Cards

题目链接 题目大意: 小明和小红各有n张卡片,每张卡片的数字是0~9; 现在小明和小红进行比赛,每次出一张卡片,每张卡片只能用一次,数字小的输; 现在问: 小红最少会输几次?还有小红最多能赢多少次?

输入数据: 第一行 数字n,表示卡片数量 (1 ≤ n ≤ 1000) 第二行 n个字符,0~9组成,表示小明的卡牌; 第三行 n个字符,0~9组成,小时小红的卡片;

输出数据: 第一行,一个整数,表示小红最少输次数;

Examples input 3 123 321 output 0 2 样例解释: 最少输的出牌顺序是小明vs小红 : 123vs123; 最多赢的出牌顺序是小明vs小红 : 123vs231;

题目解析: 分情况讨论,先看最少输的情况: 如果希望小红尽可能少输,那么应该让小红每个数字尽可能找大于等于小明的数字进行匹配; 于是可以采取这种的策略:对于每个数字,尽可能找与之最近的数字;

最多赢的情况: 如果希望小红尽可能多赢,那么应该让小红每个数字尽可能大于小明的数字进行匹配即可。

    int n;
    cin >> n;
    
    cin >> a >> b;
    int ansMin = 0;
    for (int i = 0; i < n; ++i) {
        int id = -1, dif = 100;
        for (int j = 0; j < n; ++j) {
            if (!vis[j] && b[i] >= a[j]) {
                if (b[i] - a[j] < dif) {
                    id = j;
                    dif = b[i] - a[j];
                }
            }
        }
        if (id != -1) {
            vis[id] = 1;
            ++ansMin;
        }
    }
    int ansMax = 0;
    memset(vis, 0, sizeof(vis));
    for (int i = 0; i < n; ++i) {
        int id = -1, dif = 100;
        for (int j = 0; j < n; ++j) {
            if (!vis[j] && b[i] > a[j]) {
                if (b[i] - a[j] < dif) {
                    id = j;
                    dif = b[i] - a[j];
                }
            }
        }
        if (id != -1) {
            vis[id] = 1;
            ++ansMax;
        }
    }
    cout << n - ansMin << " " << ansMax << endl;

题目5.Alyona and Spreadsheet

题目链接 题目大意: 给出n行数据,每行有m列,用a[i][j]来表示第i行,第j个数字; 我们说某一列(比如说第j列)是有序的,如果满足:对于所有的i,a[i][j] ≤ a[i+1][j]; 现在有k个询问,每个询问给出区间[l, r],在第l行到第r行是否存在有序的列,有则输出Yes,无则输出No。

输入数据 n and m (1 ≤ n·m ≤ 100 000) a[i][j] (1 ≤ a[i][j] ≤ 1e9) k (1 ≤ k ≤ 100 000) l[i] and r[i] (1 ≤ l[i] ≤ r[i] ≤ n).

输出数据 有则输出Yes,无则输出No。

Example input 5 4 1 2 3 5 3 1 3 2 4 5 2 3 5 5 3 2 4 4 3 4 6 1 1 2 5 4 5 3 5 1 3 1 5 output Yes No Yes Yes Yes No

题目解析: 我们把每一列分成多个区间,每个区间内部都是有序的;(比如说样例的第一列1,3,4,5,4就可以分成两个区间[1, 4], [5, 5]) 对于询问[l, r]即是,是否存在一个有序的区间,覆盖给定的区间[l, r]; 这题目没有要求统计[l, r]内的有序区间数量,只是询问是否存在,那么可以采用一种特殊的优化方式: 对于两个区间[l, r],我们直接用best[r]来表示r最多能达到r-l的距离; 每一个点保留能到达最远的距离,这样在询问的时候,就可以通过best[r]和(r-l)的大小,O(1)判断是否存在;

int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            int x;
            scanf("%d", &x);
            a[i].push_back(x);
        }
    }
    
    for (int j = 0; j < m; ++j) {
        dp[j] = 1;
    }
    best[0] = 1;
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (a[i][j] >= a[i - 1][j]) {
                dp[j]++;
            }
            else {
                dp[j] = 1;
            }
            best[i] = max(best[i], dp[j]);
        }
    }
    
    
    int k;
    cin >> k;
    while (k--) {
        int l, r;
        cin >> l >> r;
        --r, --l;
        if (best[r] >= r - l + 1) {
            cout << "Yes" << endl;
        }
        else {
            cout << "No" << endl;
        }
    }

总结

题目1,简单的实现题; 题目2,动态规划,需要考虑边界情况,最容易被当成贪心; 题目3,题目看起来很复杂,用二分可以很容易解决; 题目4,分类讨论,各自用贪心解决; 题目5,先考虑暴力解法,然后发现有大量重复操作,增加预处理,问题解决;

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

我来说两句

0 条评论
登录 后参与评论

相关文章

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

    题目链接 题目大意: 给出整数x,求两个整数a和b,满足: ???(?,?)+???(?,?)=? . GCD是最大公约数; LCM是最小公约数;

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

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

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

    前言 坚持做算法练习对开发的好处是抽象能力变强,拿到一个需求能很快对其进行抽象,然后再用学过的设计模式相关知识进行整理,最后用代码实现。 最大的好处在于:对...

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

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

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

    题目链接 题目大意: 有三堆石头,分别有a、b、c个; 现在可以执行操作: 1、从第一堆拿出1个石头,第二堆拿出2个石头; 2、从第二堆拿出1个石头,...

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

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

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

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

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

    前言 已经有三个月未更新算法文章,大厂工作环境是步步紧逼的,使得所有的人越来越忙碌。余下的学习时间,要用于技术预研、知识面开阔、底层原理理解等等,慢慢算法只能占...

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

    题目链接 题目大意: n个学生参加测试,一共有m道题,每道题的答案可能是(A, B, C, D , E)中的一个; m道题分别有?1,?2,…,??,共m...

    落影

扫码关注云+社区

领取腾讯云代金券