Luogu-P4053

题面

简单来说,你拥有n个破损的建筑,第 $i$ 个建筑需要 $cast_i$的时间才能修好,而如果当前时间超过了$t_i$还没有修好,这个建筑就炸掉了。

现在问你你最多可以修多少建筑

首先想到贪心,按照报废的时间从小到大排序能修就休,但是如果某个建筑的维修时间特别长而报废时间很短,选择了他就无法选择后面的建筑。这种贪心方法很显然存在问题。

那该怎么做呢?考虑带“反悔”的贪心,依旧按照报废时间排序,把每次选择的建筑话费时间加入优先队列。如果对于第$i$建筑剩余的时间不足以维修但堆顶部的时间大于此时间,那么此时反悔(不修堆顶的那个建筑,转而修当前这个。显然会使得花费的时间变小)。

代码:

1
#include <iostream>
2
#include <algorithm>
3
#include <vector>
4
#include <climits>
5
#include <queue>
6
7
using namespace std;
8
using lint = long long;
9
10
struct House {
11
    lint cast;
12
    lint upt;
13
};
14
vector<House> hs;
15
priority_queue<lint> Q;
16
17
int main() {
18
    ios::sync_with_stdio(false);
19
    cin.tie(nullptr);
20
    cout.tie(nullptr);
21
    int n;
22
    cin >> n;
23
    for (int i = 0; i < n; ++i) {
24
        lint c, u;
25
        cin >> c >> u;
26
        hs.push_back(House{c, u});
27
    }
28
    sort(hs.begin(), hs.end(), [](const House & a, const House & b) {
29
        return a.upt < b.upt;
30
    });
31
    lint cast = 0;
32
    int cnt = 0;
33
    for (auto &&h : hs) {
34
        if(cast + h.cast <= h.upt) {
35
            ++cnt;
36
            cast += h.cast;
37
            Q.push(h.cast);
38
        } else {
39
            auto t = Q.top();
40
            if(h.cast < t) {
41
                cast = cast - t + h.cast;
42
                Q.pop();
43
                Q.push(h.cast);
44
            }
45
        }
46
    }
47
    cout << cnt << endl;
48
    return 0;
49
}

CF1296D

题面

题目大意是:你和你的对手一起打小怪兽,$n$个小怪兽排成一排且各自有自己的血量,你和你的对手攻击力分别是$a$和$b$,回合制打怪兽,你先打然后轮到对手然后又轮到你以此类推,你和你的对手每打一下小怪兽会扣除攻击者攻击力的生命,如果最后你打死了怪兽你就能得到一分,如果对手打死了怪兽则你不得分(题目要求按顺序打怪兽)

并且作为一名科学家,你拥有一些特殊的科(外)技(挂),你的科技可以使用$k$次,每一次使用的可以跳过你对手的一个回合,现在问你你最多可以的多少分。

Read More

Luogu-P3119

题面

很有意思的一道题

约翰有n块草场,编号1到n,这些草场由若干条单行道相连。奶牛贝西是美味牧草的鉴赏家,她想到达尽可能多的草场>去品尝牧草。

贝西总是从1号草场出发,最后回到1号草场。她想经过尽可能多的草场,贝西在通一个草场只吃一次草,所以一个草场>可以经过多次。因为草场是单行道连接,这给贝西的品鉴工作带来了很大的不便,贝西想偷偷逆向行走一次,但最多只能有一次逆行。问,贝西最多能吃到多少个草场的牧草。

Read More

Luogu-P4832

题面

题目大意是珈百璃不想写作业就把作业交给了你,给你一些形如s+c的式子,其中s代表 $sin\frac{\pi}{7}$ ,c代表 $cos\frac{\pi}{7}$ ,然后你可以从中间选一些式子,要求最后选出的式子之和为整数最大

Read More

Luogu-P1941

题面

题目大意是要玩一个类似Flappy Bird的游戏,输入会给出地图以及每个x坐标对应的数据。小鸟每秒前进一格,可以在1s内连续点很多下让小鸟上升,也可以不点让他下降,对于每个不同的横坐标x上升和下降的值都不同,问你最少点多少下能让小鸟到达终点,如果到不了终点那么最远可以走多远。(具体题目看题面吧)

Read More

Luogu-P5322

题面

题目大意

小C正在玩一款排兵布阵的游戏。在游戏中有 $n$ 座城堡,每局对战由两名玩家来争夺这些城堡。每名玩家有 $m$ 名士兵,可以向第$i$座城堡派遣 $a_i$ 名士兵去争夺这个城堡,使得总士兵数不超过 $m$。
如果一名玩家向第 $i$ 座城堡派遣的士兵数严格大于对手派遣士兵数的两倍,那么这名玩家就占领了这座城堡,获得 $i$ 分。

现在小C即将和其他 $s$ 名玩家两两对战,这 $s$ 场对决的派遣士兵方案必须相同。小C通过某些途径得知了其他 $s$ 名玩家即将使用的策略,他想知道他应该使用什么策略来最大化自己的总分。
其中

且有

你需要输出小C总分的最大值

Read More

Luogu-P2979

题面

题意大概为给你一些种类的奶酪,每种奶酪都有自己的价值与高度,要求你用这些奶酪搭建一座奶酪塔,塔高不超过T且要求塔的总价值最大。定义高度超过K的奶酪为大奶酪,大奶酪会将其下边的奶酪高度压缩为原有的4/5(被压缩过则不再压缩)。

Read More