前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >程序员进阶之算法练习(四十三)

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

作者头像
落影
发布2020-05-26 22:23:42
2690
发布2020-05-26 22:23:42
举报
文章被收录于专栏:落影的专栏

正文

题目1

题目链接 题目大意: 屏幕上有a*b个像素点,其中第(x、y)个像素点已经损坏;(x和y从0开始) 现在想在屏幕上选出一个矩形,这个矩形的边与屏幕的边缘平行,并且不包括损坏的像素点(x,y); 问这个矩形的最大面积是多少?

输入: 第一行 整数? (1≤?≤10^4) 接下来t行,每行4个整数 ?,?,? and ? (1≤?,?≤104; 0≤?<?; 0≤?<?)

输出: 每个样例一行,每行一个整数,表示最大的面积数。

Examples input 1 8 8 0 0 output 56

样例解释-最大的面积7*8=56

题目解析:

只有四种可能,损坏点的上下左右。 如下图,假设是损坏点在红色点,那么红色点上面、左边的两种情况必然如下。

再考虑损坏点右边、下面,选取最大值即可。

代码语言:javascript
复制
    int t;
    cin >> t;
    while (t--) {
        int n, m, x, y;
        cin >> n >> m >> x >> y;
        int ans = 0;
        ans = max(ans, x * m);
        ans = max(ans, (n-x-1) * m);
        ans = max(ans, n * y);
        ans = max(ans, n * (m-y-1));
        cout  << ans << endl;
    }
题目2

题目链接 题目大意: 小明放学回家,要经过若干个公交车站;每个地方都有公共交通工具可以到达,如果是公交车,我们用A来表示;如果是地铁,我们用B来表示; 公交车的费用是a,之后连续的公交车站都可以免费到达; 地铁的费用是b,之后连续的地铁站都可以免费到达; 以AABBBAB为例,如果从第一个站开始,通过公共交通到达最后一个站,小明需要买三次票: 公交车1次,可以经过AA; 地铁1次,可以经过BBB; 公交车1次,可以经过A;(A下车之后就到达目的地B了,不需要买票)

现在小明身上之后p块钱,可能钱不够所有的交通费用,需要走路到某个站开始乘坐公共交通工具,小明想知道最少要走到哪一站?(从左到右)

输入: 第一行 整数? (1≤?≤10^4) 接下来t个样例,每个样例两行 第一行3个整数 ?,?,? (1≤?,?,?≤10^5) 第二行n个字符

输出: 每个样例一行,每行一个整数k,表示最少要步行到第k个站。

Examples input 5 2 2 1 BB 1 1 1 AB 3 2 8 AABBBBAABB 5 3 4 BBBBB 2 1 1 ABABAB

output 2 1 3 1 6

题目解析: 用逆推的方式,从最后一个站开始往前考虑。 从倒数第二个开始,假设小明当前持有的票是cur,根据cur=A或者cur=B,可以知道当前他是否需要买票; 然后倒着遍历,直到钱不够,得到正确答案。

考察的是实现的巧妙程度和边界处理。

代码语言:javascript
复制
    int t;
    cin >> t;
    while (t--) {
        int a, b, p;
        
        cin >> a >> b >> p;
        cin >> s;
        
        char cur = 0;
        int pos = (int)strlen(s) - 2;
        while (pos >= 0) {
            if (cur == s[pos]) {
                --pos;
                continue;
            }
            else {
                int cost = s[pos] == 'A' ? a : b;
                if (p >= cost) {
                    p -= cost;
                    cur = s[pos];
                    --pos;
                    continue;
                }
                else {
                    break;
                }
            }
        }
        cout << pos + 2 << endl;
    }
题目3

题目链接 题目大意: 给出n个整数b[i],现在希望构造一个数组,包括2n整数a[i]; 这个数组字典序尽可能的小,并且满足 ?[?]=min(?[2?−1],?[2?]);

输入: 第一行 整数? (1≤?≤10^4) 接下来t个样例,每个样例两行 第一行1个整数n, (1≤?≤100). 第二行n个整数b[i] (1≤b[i]≤2?)

输出: 每个样例一行,每行2n个整数;

Examples input 5 1 1 2 4 1 3 4 1 3 4 2 3 4 5 5 1 5 7 2 8

output 1 2 -1 4 5 1 2 3 6 -1 1 3 5 6 7 9 2 4 8 10

题目解析: 从要求来看,就是最终的结果是2个就有1个原来的数字; 由于字典序要求最小,并且?[?]是min(?[2?−1],?[2?]),所以b[i]肯定是放在前面的位置; 整个构造的数组是b[0], x, b[1], x, b[2], x.... 问题变成,如何在1~2n的数字中,找到合适的数字分配到x的位置中。 按照题目的要求,可以每次从1~2n中没出现的数字找到一个,然后分到x中;如果所有合法的数字都不存在,则题目无解。

考察的是构造能力。

代码语言:javascript
复制
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        memset(mp, 0, sizeof(int) * (n * 2 + 1));
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
            mp[a[i]] = 1;
        }
        
        int ok = 1;
        vector<int> ans;
        for (int i = 0; i < n; ++i) {
            ans.push_back(a[i]);
            int find = 0;
            for (int j = a[i] + 1; j <= 2*n; ++j) {
                if (!mp[j]) {
                    find = 1;
                    mp[j] = 1;
                    ans.push_back(j);
                    break;
                }
            }
            if (!find) {
                ok = 0;
                break;
            }
        }
        
        if (!ok) {
            cout << -1 << endl;
        }
        else {
            for (int i = 0; i < n*2; ++i) {
                cout << ans[i] << " ";
            }
            cout << endl;
        }
    }
题目4

题目链接 题目大意: 有n个整数a[i]的数组,现在可以对数组的数字分别进行一个操作: 令某个数a[i]=a[i]+1,但是代价是t[i]; 现在希望数组中没有重复的数字,问最小的代价是多少?

输入: 第一行1个整数n, (1≤?≤200000). 第二行n个整数?[?] (1≤?[?]≤10^9). 第二行n个整数?[?] (1≤?[?]≤10^5);

输出: 一个整数m,代表最小的代价;

Examples input 5 3 7 9 7 8 5 2 5 7 5

output 6

题目解析: 先考小数据的情况,当有两个数字相同时,我们会把代价最大的留着,代价小的数字+1; 当有3个数字相同时(假设都是x),我们我们会按照代价从大到小的分配x/x+1/x+2; 同理,当有若干个数字相同时,同样可以按照代价从大到小排序。

再回过来看题目的数据,我们从小到大来分析数据; 如果某个数字只有1个,则直接跳过; 如果某个数字出现2个以上,则最大代价的数字留着,其他的数字需要加一;

考虑到当数字x到数字y之间,会存在某些区间也可以分配数字,那么我们同样需要按照代价从大到小去分配;

每个数字只会分配一次,保持代价从大到小,可以使用优先队列,整体的复杂度是O(NLogN),在题目可接受范围内。

代码语言:javascript
复制
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        scanf("%d", &node[i].first);
    }
    for (int i = 0; i < n; ++i) {
        scanf("%d", &node[i].second);
    }
    sort(node, node + n, cmp);
    priority_queue<Node> pq;
    lld pos = 0, lastValue = 0;
    lld ans = 0;
    while (pos < n) {
        lld val = node[pos].first;
        // 在处理每组,第一个数字之前,先把之前能填补的数字补上
        lld cnt = val - lastValue;
        while (cnt > 0 && !pq.empty()) {
            Node top = pq.top();
            pq.pop();
            ans += (lastValue - top.first) * top.second;
            
            ++lastValue;
            --cnt;
        }
               
        // 把这一组的数字加上
        while (pos < n && node[pos].first == val) {
            pq.push(node[pos]);
            ++pos;
        }
        
        lastValue = val;
    }

    lastValue = node[n - 1].first;
    while (!pq.empty()) {
        Node top = pq.top();
        pq.pop();
        ans += (lastValue - top.first) * top.second;
        ++lastValue;
    }
    
    cout << ans << endl;

总结

题目1是分类讨论; 题目2思路直接,但是实现过程容易有边界问题; 题目3用优先队列,比较容易解决; 题目4也是贪心的思路,加上排序;

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 正文
    • 题目1
      • 题目2
        • 题目3
          • 题目4
          • 总结
          领券
          问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档