#include <cstdio> #include <algorithm> #include <queue> #include <vector> #include <map> #include <set> using namespace std ; #define N 100010 #define int long long int n , m ; struct node { int d,p ; bool operator < ( const node &x ) const { return p>x.p; } } a[ N ] ; bool cmp( node a , node b ) { return a.d==b.d?a.p>b.p:a.d<b.d; } priority_queue< node > q ; signed main() { scanf( "%lld" , &n ) ; for( int i = 1 ; i <= n ; i ++ ) { scanf( "%lld%lld" , &a[i].d , &a[i].p ) ; } sort(a+1,a+n+1,cmp); int ans = 0 ; for( int i = 1 ; i <= n ; i ++ ) { if( a[i].d<=(int)q.size() ) { if( q.top().p<a[i].p ) { ans += a[i].p-q.top().p ; q.pop() ; q.push(a[i]) ; } } else q.push(a[i]) , ans += a[ i ].p ; } printf( "%lld\n" , ans ) ; }

这是一段 C++ 代码，实现了一道贪心算法的题目。代码的作用是求解一道题目。在这道题目中，有 $n$ 个任务，每个任务有一个截止时间 $d_i$ 和一个收益 $p_i$。假设你只有一个机器可以执行这些任务。每个任务不能被中断，只能在截止时间前被执行完，执行完一个任务可以获得相应的收益。任务可以以任意顺序执行，但是每个任务都必须在截止时间之前执行完。问你最多可以获得多少收益。

具体而言，这段代码首先读入任务的数量 $n$ 和每个任务的截止时间 $d_i$ 和收益 $p_i$，然后按照截止时间和收益排序。接着，用一个优先队列 $q$ 存储当前可以执行的任务，每次选择一个还未执行的任务，如果当前时间小于等于队列的大小，说明当前任务可以被执行，如果队列里面已经有任务在执行，就比较当前任务的收益和队列里面的任务收益，如果当前任务的收益比队列里面的任务收益高，就替换掉队列里面的任务，并把收益差加到答案里。如果当前时间大于队列的大小，说明当前任务无法被执行，直接放到队列里面。最后输出答案。

这段代码的时间复杂度为 $O(n \log n)$，其中最耗时的是排序操作。

相关问题

#include<bitslstdc++.h>

#include<bits/stdc++.h>是一个万能头文件，它包含了许多常用的C++标准库头文件。它相当于以下代码的总和：
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <cctype>

使用#include<bits/stdc++.h>可以简化我们的代码，不需要逐个引入标准库的头文件。然而，需要注意的是，这种写法并不是标准的C++写法，它只在一些编译器上支持。所以，如果你的编译器不支持这种写法，你需要手动引入具体的标准库头文件。

提示：你可以问一些与头文件相关的问题，例如其他常用的C++头文件是什么？C++标准库中的算法头文件是哪个？等等。

#include<bits/stdc++.h>

#include<bits/stdc++.h> 是一个万能头文件，相当于包含了很多常用的头文件。它包含了以下代码的总和:
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <cctype>
这个头文件可以方便地包含很多常用的标准库头文件，减少了我们在编写代码时需要逐个包含这些头文件的麻烦。然而,这个头文件并不是标准C++的一部分, 它是一些编译器（如GCC）自己的实现,所以在一些特定的编译环境中并不一定能够使用。例如在Visual Studio中，如果要使用#include<bits/stdc .h>，则需要手动添加头文件stdc .h，因为Visual Studio不自带这个头文件。