没办法，上周疯狂双休日导致三场Codeforces和两场LeetCode的总结还没写，慢慢补吧；
学长出题挺不错的，就是有亿点难；
下次不拿命换一血了，人都要没了。
做题情况 & 练习总结
- 真的，再也不拿命换一血了，代价有亿点大；
- 前面几题因为已经在洛谷做过了，所以就直接“跳过国策”了；
- 为了拿一血所以后面就乱序了，面对一堆蓝题陷入沉思……然后见到ON题的时候感到如释重负。
A – 八皇后 Checker Challenge
深搜入门题。看着自己三年前起的奇奇怪怪的变量名陷入沉思。说不定等大学毕业了写一个《再见ACM》的时候也会对着自己四年前满屏的LL陷入沉思。厨力IP一直在换，只有Competitive Programming坚持了五年（其实太咸鱼了一直在仰卧起坐）。
扯得有点远了，作为入门题，只要判断状态是否合法即可，剪枝的东西不多。
（不放代码的题一般是几年前写的，代码过于丑旧，且会出现一堆智熄定义和变量名）
B – 马的遍历
哇，自己当年竟然为了一个入门题手写了一个队列struct，然后就去用STL了（乐）。
宽搜入门题。
C – 填涂颜色
当年用了一个匪夷所思却可行的操作：因为中间的0肯定会被1包围着，所以就先沿着周围上色把周围全填上，然后找0.
D – 奇怪的电梯
现在写的代码，注意把已经比答案大的全部剪枝掉，因为他们再怎么走也无法对最小值产生影响。已经走过的点再走一遍也还是一样的操作，所以也剪掉。
#include<bits/stdc++.h>
using namespace std;
int n,a,b,ai[10000],ans=0x7ffffff;
bool vis[10000];
void dfs(int cur,int sum){
if(cur == b) {
ans = min(sum,ans);return;
}
if(sum > ans) return;
vis[cur] = true;
if(cur + ai[cur] <= n && !vis[cur + ai[cur]]) dfs(cur + ai[cur],sum + 1);
if(cur - ai[cur] >= 1 && !vis[cur - ai[cur]]) dfs(cur - ai[cur],sum + 1);
vis[cur] = false;
return;
}
int main(){
memset(vis,false,sizeof(vis));
scanf("%d%d%d",&n,&a,&b);
for(int i=1;i<=n;i++){
scanf("%d",&ai[i]);
}
//vis[a] = true;
dfs(a,0);
printf("%d\n",ans != 0x7ffffff ? ans : -1);
return 0;
}E – 吃奶酪
用的是与上面一样的深搜剪枝，把大于已知最小答案的全部剪掉。本来想复习状压dp的，结果只拿来用作状态记录，实在浪费。注意遍历开始时有一个从(0,0)到起始点的初值。
#include<bits/stdc++.h>
using namespace std;
double ai[20][2],dis[20][20],dp[20][60000];
int n;double ans=100000000;
void dfs(int cur,int sta,double sum){
if(sta==(1<<n)-1){
ans = min(ans,sum);
return;
}
if(sum>ans)return;
if(dp[cur][sta]!=-1 && dp[cur][sta]<=sum)return;
dp[cur][sta] = sum;
for(int i=1;i<=n;i++){
if((1<<(i-1))&sta)continue;
dfs(i,(1<<(i-1))|sta,sum+dis[cur][i]);
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%lf%lf",&ai[i][0],&ai[i][1]);
dis[0][i]=sqrt(pow(ai[i][0],2)+pow(ai[i][1],2));
for(int j=0;j<(1<<n);j++)dp[i][j]=-1;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++){
dis[i][j] = sqrt(pow(ai[i][0]-ai[j][0],2)
+ pow(ai[i][1]-ai[j][1],2));
dis[j][i] = dis[i][j];
}
for(int i=1;i<=n;i++)dfs(i,1<<(i-1),dis[0][i]);
printf("%.2f\n",ans);
return 0;
}F – 迷宫
数据范围不大，宽搜深搜均可。
G – 并查集
模板题
H – 朋友
偷懒用Python写了。由于两个公司一个取正一个取负所以可以偷懒全部塞到一个并查集里。一开始没发现是“同时组成CP”（取最小值）而不是“可以组成CP的总数量”（乘法原理）。
本人所有的并查集在没有特殊说明的情况下，默认在查找的时候采用路径压缩优化。
s = input().split()
n = int(s[0])
m = int(s[1])
p = int(s[2])
q = int(s[3])
if True:
ReallySorry = {} # 各节点的父亲节点
tokimeki = {} # 各并查集的数量和
for i in range(n+1):
ReallySorry[i] = i # 初始父亲节点就是自己
tokimeki[i] = 1
for i in range(-m,0):
ReallySorry[i] = i # 初始父亲节点就是自己
tokimeki[i] = 1
# 并查集查询函数
def getFather(i):
if ReallySorry[i] == i : return i
fa = getFather(ReallySorry[i])
# tokimeki[fa] += tokimeki[i]
ReallySorry[i] = fa
return ReallySorry[i]
def mergeDD(a,b):
fa = getFather(a)
fb = getFather(b)
if fa == fb : return
tokimeki[fa] += tokimeki[fb]
ReallySorry[fb] = fa
for i in range(p + q):
s = input().split()
mergeDD(int(s[0]),int(s[1]))
print(min(tokimeki[getFather(1)],tokimeki[getFather(-1)]))I – Cube Stacking
大脑热身题。以堆底作为并查集的root，用dis[i]作为当前箱子到当前堆底的距离，len[i]作为当前堆的总长度（仅对堆底root节点有意义）。
#include<iostream>
#include<cstdlib>
#include<cstring>
using namespace std;
int fa[50000],len[50000],dis[50000];
int n,m,xa,xb;char xc;
inline int getfa(int i){
if(i==fa[i])return i;
int ffa = getfa(fa[i]);
dis[i] += dis[fa[i]];
//由于每次遍历都会伸到堆底，所以对于已经完成
//路径压缩的并查集，dis[fa[i]]恒为0.
fa[i] = ffa;
return fa[i];
}
inline void merge(int a,int b){
//这题在合并的时候注意方向，这里是将a堆到b的上面
int aroot=getfa(a),broot=getfa(b);
fa[aroot]=broot;
dis[aroot]+=len[broot];
//其中的节点会在查找并进行路径压缩的时候处理此次变更
len[broot]+=len[aroot];
}
inline int count(int a){
int aroot = getfa(a);
//为了触发可能存在的未处理改变需要虚空执行一次
return dis[a];
}
int main(){
memset(dis,0,sizeof(dis));
cin>>m;
for(int i=1;i<=50000;i++)fa[i]=i,len[i]=1;
while(m--){
cin>>xc;
if(xc=='M'){
cin>>xa>>xb;
merge(xa,xb);
}else{
cin>>xa;
cout<<count(xa)<<endl;
}
}
return 0;
}J – Junk-Mail Filter
是可删除并查集！于是现学了一下处理方法：《并查集 #删除 – OI Wiki》。但是！注意这题可能会存在多次删除添加的操作，所以当前面的内容不存在。但思路其实差不多。
正确的做法是：建一个映射数组，代表每个实际节点对应的并查集节点。每次孤立节点的时候就新开一个并查集节点，并把该实际节点映射到新的并查集节点上，同时老的并查集节点，仍然储存着并查集节点之间关系。因为只会遍历数组里的并查集节点，所以那些没有对应实际节点的并查集节点（包括反复增删出现的大量没用的空节点，和仅用于表示节点之间连接关系的“虚空”并查集节点）不会对答案（有“对应实际节点”存在的并查集的数量）产生影响。
#include<iostream>
#include<algorithm>
#include<set>
#include<map>
#include<cstring>
using namespace std;
int fa[1100006],mp[1100006],n,m,cnt,cacnt;
int a,b,ans;char c;bool flag[1100006];
int getfa(int x){
if (x==fa[x])return x;
fa[x]=getfa(fa[x]);
return fa[x];
}
void merge(int x,int y){
int fx=getfa(x),fy=getfa(y);
if(fx==fy)return;
fa[fy]=fx;
}
void del(int x,int yuanlai){
mp[yuanlai] = ++cnt;
fa[cnt] = cnt;
}
int main(){
cacnt=1;
while(~scanf("%d%d",&n,&m)&&(n||m)){
cnt=n;
memset(flag,false,sizeof(flag));
for(int i=1;i<=n;i++){
fa[i] = i;mp[i-1] = i;
}
while(m--){
c = ' ';
while(c!='M'&&c!='S') c = getchar();
if(c=='M'){
scanf("%d%d",&a,&b);
merge(mp[a],mp[b]);
}else{
scanf("%d",&a);
del(mp[a],a);
}
}
ans = 0;
for(int i=0;i<n;i++){
if(!flag[getfa(mp[i])]){
flag[getfa(mp[i])] = true;
ans++;
}
//cout<<getfa(i->second)<<" ";
}//cout<<endl;
printf("Case #%d: %d\n",cacnt,ans);
cacnt++;
}
}//ReallySorryK – 食物链
这题使用神奇的“种类并查集”，因为过于神奇（好吧其实是因为我菜）所以要多唠叨两句。
好吧，其实是我一开始漏条件了，然后就没想通:(。题目明确写出了：动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B， B吃C，C吃A。而不是我想象中的N种不同的动物……
并查集不仅可以表示“同类”关系，还可以通过在不同集合之间形成联系，形成表示多种关系的“种类并查集”。对于物种A，物种B是它的猎物，物种C是它的天敌。因为题目中明确说了是三类物种的恩怨关系，并且存在“同类，猎物和天敌”三种关系，所以需要开三倍于节点数量的并查集：处理物种对应$[1,n]$（$a_i = i$），猎物物种对应$[n+1,2n]$（$b_i = n + i$）,天敌物种对应$[2n+1,3n]$（$c_i = 2n + i$）。注意：种类并查集中相连的节点表示的是“存在关系”，在进行接下来的处理的时候需要时刻注意这一点。
在处理同类关系的时候，同类之间只要在同类范围之间连接即可。但是！别忘了对于其他物种来说，他们需要处理的天敌和猎物关系也会变。所以，我们也需要在“猎物物种”和“天敌物种”之间进行类似操作。
在处理食物链关系的时候操作略显复杂。由于存在吃与被吃的关系，我们需要在“处理物种”中的捕食者X和“猎物物种”中的被捕食者Y中连接，表示它们之间存在关系。因为他们的并查集节点分属于两个不同的集合，所以可以轻易地通过节点编号判断吃与被吃的关系。同理，我们需要在“处理物种”中的被捕食者Y和“天敌物种”中的捕食者X中连接，表示它们之间存在关系。因为“有趣的环形”（若已知A吃B，B吃C，必存在C吃A）的存在，为了第三方物种的利益，我们还需要在“猎物物种”中的捕食者X和“天敌物种”中的被捕食者Y中连接，表示它们之间存在关系。
这样建模下来，最后判断一句话是不是假话就很简单了。如果在处理同类关系的时候，发现了这两个物种存在食物链关系，或者处理食物链关系的时候，发现了这两个物种存在同类关系——直接回怼他一句：“FAKE！”
#include<cstdio>
using namespace std;
int fa[150005],n,m,a,b,c;
int cnt,fake;
inline int getfa(int x){
if(fa[x]==x)return x;
fa[x] = getfa(fa[x]);
return fa[x];
}
inline void merge(int x,int y){
int fx=getfa(x),fy=getfa(y);
fa[fx] = fa[fy];
}
int main(){
scanf("%d%d",&n,&m);cnt = 0;fake = 0;
for(int i=1;i<=n*3;i++)fa[i] = i;
for(int i=1;i<=m;i++){
//当前处理 当前的猎物 当前的天敌
scanf("%d%d%d",&a,&b,&c);
if(b>n || c>n){
fake++;continue;
}
if(a==1){
if(getfa(c)==getfa(n+b)||getfa(b)==getfa(n+c)){
fake++;
}else{
merge(c,b);merge(n+c,n+b);merge(2*n+c,2*n+b);
}
}else{
if(getfa(b)==getfa(c)||getfa(b+n)==getfa(c)){
fake++;
}else{
merge(b,c+n);merge(b+n,c+2*n);merge(b+2*n,c);
}
}
}
printf("%d\n",fake);return 0;
}L – 单调栈
模板题，但是之前没刷过，于是留下代码。注意题目中需要严格大于。
#include<bits/stdc++.h>
using namespace std;
stack<pair<int,int> > sta;
pair<int,int> cur;
int ans[3000005];
int n,tmp;
int main(){
scanf("%d",&n);memset(ans,0,sizeof(ans));
for(int i=1;i<=n;i++){
scanf("%d",&tmp);
while(sta.size() and sta.top().first < tmp){
ans[sta.top().second] = i;sta.pop();
}
sta.push(make_pair(tmp,i));
}
for(int i=1;i<=n;i++)printf("%d ",ans[i]);
printf("\n");return 0;
}M – Largest Rectangle in a Histogram
双向单调栈，需要同时记录该节点的高度和其能像左/右侧延伸的最远节点。
#include<bits/stdc++.h>
using namespace std;
int l[100006],r[100006],ai[100006];
int n;stack<int> sl,sr;
long long ans;
int main(){
scanf("%d",&n);
while(n!=0){
ans = 0;
stack<int> sl,sr;
for(int i=1;i<=n;i++){
scanf("%d",&ai[i]);
l[i] = i;r[i] = i;
}
for(int i=1;i<=n;i++){
while(!sl.empty()&&ai[sl.top()]>=ai[i])sl.pop();
l[i] = sl.empty() ? 1 : sl.top() + 1;
sl.push(i);
}
for(int i=n;i>=1;i--){
while(!sr.empty()&&ai[sr.top()]>=ai[i])sr.pop();
r[i] = sr.empty() ? n : sr.top() - 1;
sr.push(i);
ans = max(ans,(long long)(r[i]-l[i]+1)*ai[i]);
}
printf("%lld\n",ans);
scanf("%d",&n);
}
}N – 最大矩形III
因为之前冲一血，把这一题放到了最后一道。总结了之前的经验教训，自己也慢慢地学会建模了。
首先，采用了固定矩形左上角并向右向下拓展的方法数数，所以事先对每一个格子按照行从右到左进行预处理，求出当前行向右所能拓展到的最大宽度。
在处理的时候按照列从下到上（因为是以左上角为基准数数）处理数据。由于“瓶颈”的存在，采用自下而上单调递增的单调栈进行优化。单调栈内储存[0]:行向右最远的拓展；[1]:行底部的标号（处理“瓶颈”时需要用到，“瓶颈”行之下的行统一看做“瓶颈”行的大小）；[2]:之前处理的答案（优化的重点，因为数数实际上是一个确定矩形右下角的过程，之前能用来当做右下角的点，在当前行不窄于“瓶颈”行的状态下也可以作为右下角）。
#include<bits/stdc++.h>
using namespace std;
bool tree[5005][5005];
int cntri[5005][5005];
long long sta[5005][3];
long long ans=0;
int n,m,a,b,maxl,cur,stacnt;
int main(){
memset(tree,0,sizeof(tree));
memset(cntri,0,sizeof(cntri));
scanf("%d%d",&n,&m);
while(m--){
scanf("%d%d",&a,&b);
tree[a][b] = true;
}
for(int i=1;i<=n;i++){
for(int j=n;j>=1;j--){
cntri[i][j] = (tree[i][j] ? 0 : cntri[i][j+1] + 1);
}
}
for(int j=1;j<=n;j++){
stacnt = 0;
for(int i=n;i>=1;i--){
if(tree[i][j]){
stacnt = 0;continue;
}
cur = i;
while(stacnt&&sta[stacnt][0]>cntri[i][j]){
cur = sta[stacnt][1]; stacnt--;
}
sta[++stacnt][0] = cntri[i][j];
sta[stacnt][1] = cur;
sta[stacnt][2] = (long long)sta[stacnt][0] * (cur - i + 1) + sta[stacnt-1][2];
ans += sta[stacnt][2];
}
}
printf("%lld\n",ans);return 0;
}由于时间太晚，来不及码了，仅留下主要思考过程。
O – Permutation Graph
分治解法，没用单调栈。
#include<bits/stdc++.h>
using namespace std;
namespace ReallySorry{
int n,m,a,b,ai[250005];
int fmax[250005],bmax[250005],
fmin[250005],bmin[250005],pos[250005];
inline int solve_f(int x){
// 向前寻找，直到找到1号结点
if(x==1)return 0;
return ((ai[x]==fmax[x]) ? (solve_f(pos[fmin[x]])) : (solve_f(pos[fmax[x]]))) + 1;
}
inline int solve_b(int x){
// 向后寻找，直到找到n号结点
if(x==n)return 0;
return ((ai[x]==bmax[x]) ? (solve_b(pos[bmin[x]])) : (solve_b(pos[bmax[x]]))) + 1;
}
void main(){
scanf("%d",&n);fmax[0] = 0;fmin[0]=300000;
for(int i=1;i<=n;i++){
scanf("%d",&ai[i]);
pos[ai[i]] = i;
}
fmax[1] = fmin[1] = ai[1];
for(int i=2;i<=n;i++){
fmax[i] = max(fmax[i-1],ai[i]);
fmin[i] = min(fmin[i-1],ai[i]);
}
bmax[n] = bmin[n] = ai[n];
for(int i=n-1;i>=1;i--){
bmax[i] = max(bmax[i+1],ai[i]);
bmin[i] = min(bmin[i+1],ai[i]);
}
if(n==1){
printf("0\n");return;
}
if((pos[1]==1&&pos[n]==n)||(pos[n]==1&&pos[1]==n)){
printf("1\n");return;
}
if(pos[n]>1&&pos[n]<n) printf("%d\n",solve_f(pos[n])+solve_b(pos[n]));
else if(pos[1]>1&&pos[1]<n) printf("%d\n",solve_f(pos[1])+solve_b(pos[1]));
return;
}
}
int main(){
int _t;
scanf("%d",&_t);
while(_t--){
ReallySorry::main();
}
return 0;
}P – 滑动窗口 /【模板】单调队列
模板题
Q – Mowing the Lawn
这题想到了DP，但是一开始方程推得有问题，WA声一片。
#include<bits/stdc++.h>
using namespace std;
// 所以这道题是多组测试数据
// dp[i][0] = max{dp[i-1][1],dp[i-1][0]} 没说不能几头牛同时休息
// dp[i][1] = max{dp[j][1] + sum[i] - sum[j+1]} (0 <= j < i-k)
// = max{dp[j][1] - sum[j+1]} + sum[i] (i-k-1 <= j < i-1)
// 上面的转移方程作废（话虽然这么说还是头铁用了上面的转移方程）
// dp[i][1] = max{dp[j][0] - sum[j]} + sum[i] (i-k <= j < i)
long long sum[500005],dp[500000][2],tmp,ans;
int n,k;
int main(){
while(~scanf("%d%d",&n,&k)){
priority_queue<pair<long long,int> > q;
sum[0] = 0;
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++){
scanf("%lld",&tmp);
sum[i] = sum[i-1] + tmp;
}
sum[n+1] = 0x7f7f7f7f;
for(int i=1;i<=k;i++){
dp[i][0] = max(dp[i-1][0],dp[i-1][1]);
dp[i][1] = sum[i];
q.push(make_pair((dp[i-1][1]-sum[i]),i-1));
}
for(int i=k+1;i<=n;i++){
dp[i][0] = max(dp[i-1][0],dp[i-1][1]);
while(!q.empty()&&q.top().second<i-k-1)q.pop();
dp[i][1] = sum[i] + q.top().first;
q.push(make_pair((dp[i-1][1]-sum[i]),i-1));
}ans = 0;
for(int i=1;i<=n;i++){
ans = max(ans,max(dp[i][0],dp[i][1]));
}
printf("%lld\n",ans);
}
return 0;
}R – 理想的正方形
因为数据范围不大，所以就当成了大号的滑动窗口。是需要进行两次处理的大号滑动窗口，第二次处理直接在第一次处理的结果上做滑动窗口。
#include<bits/stdc++.h>
using namespace std;
int maxi[1005][1005],mini[1005][1005],ai[1005][1005];
int a,b,n,ans;
int main(){
scanf("%d%d%d",&a,&b,&n);
for(int i=1;i<=a;i++){
for(int j=1;j<=b;j++){
scanf("%d",&ai[i][j]);
}
}
// 维护行的最大最小值
for(int i=1;i<=a;i++){
deque<pair<int,int> > sma,smi;
for(int j=1;j<n;j++){
while(!sma.empty()&&sma.back().first<ai[i][j])
sma.pop_back();
sma.push_back(make_pair(ai[i][j],j));
while(!smi.empty()&&smi.back().first>ai[i][j])
smi.pop_back();
smi.push_back(make_pair(ai[i][j],j));
}
for(int j=n;j<=b;j++){
//维护最大值
while(!sma.empty()&&sma.back().first<ai[i][j])
sma.pop_back();
sma.push_back(make_pair(ai[i][j],j));
while(!sma.empty()&&sma.front().second<j-n+1)
sma.pop_front();
maxi[i][j-n+1] = sma.front().first;
//维护最小值
while(!smi.empty()&&smi.back().first>ai[i][j])
smi.pop_back();
smi.push_back(make_pair(ai[i][j],j));
while(!smi.empty()&&smi.front().second<j-n+1)
smi.pop_front();
mini[i][j-n+1] = smi.front().first;
}
}
// 维护列的最大最小值
for(int j=1;j<=b-n+1;j++){
deque<pair<int,int> > sma,smi;
for(int i=1;i<n;i++){
while(!sma.empty()&&sma.back().first<maxi[i][j])
sma.pop_back();
sma.push_back(make_pair(maxi[i][j],i));
while(!smi.empty()&&smi.back().first>mini[i][j])
smi.pop_back();
smi.push_back(make_pair(mini[i][j],i));
}
for(int i=n;i<=a;i++){
//维护最大值
while(!sma.empty()&&sma.back().first<maxi[i][j])
sma.pop_back();
sma.push_back(make_pair(maxi[i][j],i));
while(!sma.empty()&&sma.front().second<i-n+1)
sma.pop_front();
maxi[i-n+1][j] = sma.front().first;
//维护最小值
while(!smi.empty()&&smi.back().first>mini[i][j])
smi.pop_back();
smi.push_back(make_pair(mini[i][j],i));
while(!smi.empty()&&smi.front().second<i-n+1)
smi.pop_front();
mini[i-n+1][j] = smi.front().first;
}
}
//输出
ans = 0x7f7f7f7f;
for(int i=1;i<=a-n+1;i++){
for(int j=1;j<=b-n+1;j++){
ans = min(ans,maxi[i][j]-mini[i][j]);
}
}
printf("%d\n",ans);
return 0;
}S – Buy Figurines
背景其实是早柚买以雷军为原型的“御建鸣神主尊大御所大人像”的故事……
vector套queue逃课过的。
#include<bits/stdc++.h>
using namespace std;
namespace gusokumoshi{
pair<long long,long long> ps[300000];
int n,m;long long a,b,ans,len;
void main(){
scanf("%d%d",&n,&m);
vector<queue<int> > qs(m);
for(int i=1;i<=n;i++){
scanf("%lld%lld",&a,&b);
ps[i] = make_pair(a,a+b);
}
sort(ps+1,ps+n+1);ans=0;
for(int i=1;i<=n;i++){
int minl = 10000000,mini = 0;
bool flag=true;
for(int j=0;j<m;j++){
while(!qs[j].empty()&&
ps[qs[j].front()].second<=ps[i].first)
qs[j].pop();
if(qs[j].empty()){
mini = j;
flag=false;
ans=max(ans,ps[i].second);
qs[mini].push(i);
break;
}
if(qs[j].size()<minl){
minl = qs[j].size();
mini = j;
}
}
if (flag){
len=ps[i].second-ps[i].first;
ps[i].first=ps[qs[mini].back()].second;
ps[i].second=ps[qs[mini].back()].second+len;
ans=max(ans,ps[i].second);
qs[mini].push(i);
}
}
printf("%lld\n",ans);
}
}
int main(){
int _t;
scanf("%d",&_t);
while(_t--)gusokumoshi::main();
return 0;
}T – Hanoi Factory
因为上盘外径不大于下盘外径的时候上盘内径不可能大于下盘外径，所以少了一个条件。
从下盘往上盘推，按照外径优先内径第二的原则构造大根堆。如果当前处理的盘的外径已经比堆顶的盘的内径小了，当前盘上面的盘也一定没办法放到堆顶盘的上面，所以可以毫无顾虑地把堆顶弹掉。可以顺便在大根堆里面储存答案方便迭代计算。
#include<bits/stdc++.h>
#define ReallySorry(a,b,c) (make_pair(make_pair(a,b),c))
using namespace std;
pair<pair<long long,long long>,long long> hanoi[200005];
long long ansi[200005],ans=0,ta,tb,tc;
int n;
priority_queue<pair<long long,int> > q;
int main(){
scanf("%d",&n);ansi[0]=0;
for(int i=1;i<=n;i++){
scanf("%lld%lld%lld",&ta,&tb,&tc);
hanoi[i]=ReallySorry(tb,ta,tc);
}
sort(hanoi+1,hanoi+n+1);
for(int i=n;i>=1;i--){
while(!q.empty()&&(hanoi[q.top().second].first.second>=hanoi[i].first.first))q.pop();
if(q.empty())ta=0;
else ta=q.top().second;
ansi[i]=ansi[ta]+hanoi[i].second;
ans = max(ans,ansi[i]);
q.push(make_pair(ansi[i],i));
}
printf("%lld\n",ans);return 0;
}U – Package Delivery
按照DDL就是第一生产力的原则，尽可能把有效期较长的包裹放到后面，和后面的包裹一起取走。读入数据按照l第一r第二的方式升序，并构造小根堆方便快速取尽可能小的r。
#include<bits/stdc++.h>
using namespace std;
#define left first
#define right second
#define Pleft second
#define Pright first
int n,_t,a,b,rday,ans,k;
int main(){
scanf("%d",&_t);
while(_t--){
priority_queue<pair<int,int> > q;
pair<int,int> db[200005];
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++){
scanf("%d%d",&a,&b);
db[i] = make_pair(a,b);
}
sort(db+1,db+n+1);
q.push(make_pair(-db[1].right,-db[1].left));
rday = db[1].right;ans = 0;
for(int i=2;i<=n;){
//压缩选择空间，加入所有可选项
while(i<=n&&db[i].left<=rday||rday==-1){
if(rday==-1) rday=db[i].right;
rday = min(rday,db[i].right);
q.push(make_pair(-db[i].right,-db[i].left));
i++;
}
if(q.size()<=k){
rday=-1;
while(!q.empty()){
q.pop();
}
ans += 1;
}else{
for(int j=1;j<=k;j++){
q.pop();
}rday = -q.top().Pright;
ans += 1;
}
//cout<<endl;
}
//还剩下的包裹就向上取整
if(!q.empty()){
ans += (q.size()+k-1) / k;
}
printf("%d\n",ans);
}
return 0;
}
