无题

好久没写博客了……就把这几天在我校OJ上写的几个贪心题简单整理一下吧。

六学家的困惑

题目很短,就直接把题目放上来了:

小六面前有两根管子,管子里面放满了数字为 $1$ 到 $9$ 的小球。
每次取球时,小六会先选择一根管子,再从这根管子的某一侧(左侧或右侧)取出一个球。每一根管子最少有$1$个小球,最多有$40$个小球。
在满足取球规则的情况下,他可以任意顺序取出所有小球。假如小六依次取出的球的编号为 $a_1, a_2, \cdots, a_n$​,则他最后就得到了一个形如 $\overline {a_1 a_2 \cdots a_n}$​​ 样的十进制数。

求这样组成的最大十进制数。

基于贪心的思路,一种朴素的想法是每次取两个字符串两端共四个数的最大数。然而,这种想法对于管道两侧有相同整数的情形则无法处理:例如,对于管道$23334$和$4894$,如果我们第一次从第一根管道的末尾取$4$,那么得到的整数显然不是最大的。如果我们第一次从第二根管道$4894$的右侧取出$4$,那么我们就能够按照刚才的思路获得最大数。

这种思路的关键在于,我们能够从(两根管道)两端重复的数字中“考虑到”取这个数字给接下来的工作带来的影响:即,我们应当从接下来能够取出最大的那一端取出这个重复的数字。

那么怎么实现呢?如果我们模拟刚才的思路,处理起来其实是一件相当繁的事情。我们转换一下角度:既然是从两端取数,那么我们完全可以把两个管道变成四个管道,都从其中一端取数好了。亦即,我们把这两个字符串(应该没有人会用大整数维护长$40$位的整数的吧,很可惜__int128最大只有$39$位)翻转一下,这样子就可以从一端取数了!更幸运的是,对于刚才我们讨论含有重复数字的处理方法,这样子处理也是很方便的:这是因为,“接下来能够取出最大的那一端”翻转后和其它三个字符串相比,它的字典序肯定是最大的。

那么事情就变得很简单了:

#include <bits/stdc++.h>
using namespace std;
int main() {
    cin.sync_with_stdio(false);
    int t, kase = 0;
    string a, b, x, y;
    cin >> t;
    while (t--) {
        cin >> a >> b;
        string ans;
        while (a.length() || b.length()) {
            x = a, y = b;
            reverse(x.begin(), x.end()), reverse(y.begin(), y.end());
            a = max(x, a), b = max(y, b);
            if (a > b)
                ans += a.front(), a.erase(0, 1);    //模拟取出的操作
            else
                ans += b.front(), b.erase(0, 1);
        }
        printf("Case #%d: %s\n", ++kase, ans.c_str());
    }
    return 0;
}

其实感觉这道题最巧妙的地方还是把字符串翻转处理。不过最暴力的是,这道题最长代码长达$1188$行……orz

Tobby’s WiFi

​ $Tobby$要在宿舍装无线网。他的路由器不太好,因此需要买很多个才能让宿舍信号无死角。

​ 已知宿舍长$L(L\leq 100000)$宽$W \leq 200$,$Tobby$买了$n \leq L + 1$个路由器想在宿舍摆成一条线放开,每个路由器的安装位置$x_{i} \leq L$,有效半径$r_{i} \leq L$,问实际上最少需要几个路由器即可满足要求。

这个题和之前UVA上的一道题(放水管?)很相似(或者说就是改了个题面),实际上因为宿舍是矩形,因此根本没必要考虑所谓的那个信号覆盖圆有多大:用勾股定理先算出来每个圆覆盖的最大矩形的长$[x_{i} -\sqrt{ r_{i}^2 – \frac{w_{i}^2}{4}},x_{i} +\sqrt{ r_{i}^2 – \frac{w_{i}^2}{4}}]$,然后问题就转化为最小线段覆盖的问题了。至于宽度,如果圆的半径比$\frac{W}{2}$ 还短的话直接扔掉这个路由器就行了,因为它根本就覆盖不完。

统计的时候贪心,先按照左端点排序,然后去找更大的区间就好了。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int l, w, n, cnt = 0, ans = 0;
struct seg {
    double l, r;
    bool operator<(const seg& rhs) const {
        return l == rhs.l ? r < rhs.r : l < rhs.l;
    }
} pool[maxn];
inline void make(double x, double r) {
    if (r <= (w / 2.0)) return;
    double t = sqrt(r * r - w * w / 4.0);
    pool[++cnt] = {x - t, x + t};
}
int main() {
    cin.sync_with_stdio(0);
    while (cin >> l >> w >> n) {
        cnt = ans = 0;
        for (int i = 1; i <= n; ++i) {
            double x, r;
            cin >> x >> r;
            make(x, r);
        }
        double now = 0;
        sort(pool + 1, pool + 1 + cnt);
        if (pool[1].l > 0)
            ans = -1;
        else {
            while (now < l) {
                double maxx = now;
                for (int i = 1; i <= cnt; ++i)
                    if (pool[i].l <= now && pool[i].r >= maxx) maxx = pool[i].r;
                if (maxx == now) {
                    ans = -1;
                    break;
                }
                now = maxx, ++ans;
            }
        }
        printf("%d\n", ans);
    }
}

Catch up with homework

​ $Tobby$写作业。
​ 有$ 2 \leq n \leq 100$本作业,每本作业有一个DDL:$1 \leq t_{i} \leq 50$(单位分钟)分数$1 \leq w_{i} \leq 1000 $,要求合理分配作业完成顺序,使得$Tobby$获得的总分最大。$Tobby$一次只能写一本作业,每一本作业需要花费$1$分钟。

先对作业按照分数降序排个序吧。这样子我们每次就先安排那些分数大的作业:怎么安排?紧着DDL放。尽量放到DDL的前一分钟完成,如果有多个作业有相同的DDL,那么就把后面的作业往前依次放即可。如果前面都排满了,那么就放弃这个作业不写了。

要断网了,正确性说明稍后补上。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 105;
struct node {
    int t, s;
    bool operator<(const node& rhs) const { return s > rhs.s; }
} x[maxn];
int vis[maxn], last[maxn];
int main() {
    cin.sync_with_stdio(false);
    int n;
    while (cin >> n) {
        for (int i = 1; i <= n; ++i) {
            vis[i] = last[i] = 0;
            cin >> x[i].t >> x[i].s;
        }
        sort(x + 1, x + 1 + n);
        for (int i = 1; i <= n; ++i) last[x[i].t] = x[i].t;
        int ans = 0;
        for (int i = 1; i <= n; ++i) {
            while (last[x[i].t] && vis[last[x[i].t]]) last[x[i].t]--;
            if (!last[x[i].t]) continue;
            ans += x[i].s;
            vis[last[x[i].t]] = 1;
        }
        printf("%d\n", ans);
    }
    return 0;
}
此条目发表在计算机分类目录。将固定链接加入收藏夹。

发表评论

电子邮件地址不会被公开。 必填项已用*标注