题目链接:https://ac.nowcoder.com/acm/problem/20154
思路:
首先将每栋建筑按照截至时间排序,当然你可以用结构体排序,或者定义二维数组,二位向量啥的,但是在这里,用pair会比较简单,pair 默认对first升序(若相等,对second 升序),这样可以避免写cmp函数或者重载运算符<。
但是要注意把截止时间放在first 把花费时间放在second
接着呢 我们把从截止时间早的开始 把凡是能修的就修,
能修指 now(现在的时间点)+修理所需要的时间<=截止时间
然后我们把修理时间放到一个优先队列(大根堆)里面
这样队列里面放的就都是我们修过的建筑的修理时间了
但是这样很难是最优解,我们很快就会遇到不能修的建筑了(即now(现在的时间点)+修理所需要的时间>截止时间)
这时候我们只要拿他和我们队列中的建筑比较,如果这个建筑的修理时间比我们之前已经修过的建筑要短,那就说明修这个建筑会比修之前的建筑更值得,所以我们就去掉之前建筑中的一个建筑了,换成修现在这个修理时间更短的建筑。
(再对这个更优解释一下,我们的数组是排过序的在后面的建筑是截止时间更晚的,如果这是后这个建筑的修理时间更短,那肯定换修他方案会更优。
举例:如果两个建筑a和b只能修一个,a截止时间晚修理时间短,那你肯定修a啊)
依照这种方式,遍历完n个建筑,就能得到最优解。
细节和详情看代码和注释,写的挺清楚的了。
#include<iostream> #include<algorithm> #include<queue> #include<string> #include<cstdio> #include<cstring> #include<queue> #include<vector> #include<stack> #include<set> #include<map> #define ll long long using namespace std; #define close_stdin ios::sync_with_stdio(false) int n; const int maxn = 150007; pair<ll,ll> a[maxn]; priority_queue<int> q; //放修理的楼的 修理时间 void my_input() { //输入数据 cin >> n; for (int i = 1;i <= n;i++) { cin >> a[i].second >> a[i].first; }// 由于是要对 截止时间排序,所以把截至时间放在前面(first) } void solve() { sort(a + 1, a + 1 + n); ll now = 0; //表示当下的时间 ,由于T1 ,T2 的限制 所以必须用 longlong int cnt = 0; for (int i = 1;i <= n;i++) { //注意first是截止时间 second 是修理需要时间 if (now + a[i].second <= a[i].first) { //能修就先修着,后续再去调整 cnt++; now += a[i].second; q.push(a[i].second); //能修就把它放到q里面 } else if (a[i].second< q.top()) { //由于前面能修就修,所以不是最优,一定会发生到i的时候修不了了,这时候进行优化 now -= q.top(); //这时候 a[i] 的截止时间在 q.top对应的建筑后面而修理时间却比q.top短 所以很明显能修a[i] 并且修a【i】会更合理 now += a[i].second; q.pop(); q.push(a[i].second); //这边只是将修的建筑一换一 来调高性价比 ,所以cnt不需要++ } } cout << cnt; } int main() { close_stdin;//只是为了让cin和printf一样快 my_input(); solve(); }
谢谢浏览哈!