晨汐散余香

【题意简述】

有 $n$ 个物品，第 $i$ 个物品价值为 $w_i$，最晚在第 $t_i$ 天交易。每天至多交易一个物品。对每次询问 $p_i$，求最多使用 $p_i$ 个交易日时可以得到的最大总价值。

【Hint】

如果只问一次固定天数，价值大的物品应优先考虑，并尽量安排到不晚于截止时间的最晚空闲日。

【提示】

把物品按价值从大到小排序。若当前物品还能放进某个不超过 $t_i$ 的空闲日，则选它不会劣于把这个位置留给价值更小的物品。

【解法】

将所有物品按价值从大到小排序。使用并查集维护每个日期左侧最近的空闲位置：若要放入一个截止时间为 $t_i$ 的物品，就查询 $\operatorname{Find}(t_i)$。若得到的位置非零，则把该物品安排在此处，并将这个位置与左侧位置合并。

按这个过程依次选到第 $k$ 个物品时，得到的前缀收益就是最多使用 $k$ 个交易日的最优值。所有询问只需要输出对应前缀即可。

交换证明如下：若某个最优方案中存在一个未选的高价值物品 $A$ 和一个已选的低价值物品 $B$，且 $A$ 可以被放入当前可行日集合中，那么用 $A$ 替换 $B$ 不会降低可行性，收益只会增加。因此从高价值到低价值贪心是合法的。

【数据点到正解】

当所有失效时间相同，或所有失效时间都不小于 $n$ 时，只需把价值排序并取前缀和。一般情形中，固定一次询问后，仍按价值从大到小扫描，把当前物品放在不晚于 $\min(t_i,p)$ 的最晚空闲日；这给出了每个询问独立做贪心的做法。

正解注意到扫描顺序从不改变，变化的只有最多选择多少份。因此先不限制选择数量，完整执行一次“价值降序、最晚空闲日”的贪心。扫描到第 $s$ 个被选物品时，前缀和就是恰好选择 $s$ 份的最优值：任一可行 $s$ 元方案在其最小价值物品被扫描到时，都证明此前前缀至少能安排 $s$ 份；贪心每个前缀都选出尽可能多的物品，故其第 $s$ 个收益不会更小。

【复杂度】

并查集令被占用的日期指向左侧最近空闲日。排序复杂度为 $\mathcal{O}(n\log n)$，并查集均摊近似 $\mathcal{O}(n)$，回答询问为 $\mathcal{O}(q)$。

【参考代码】

1/*2Author:Ehundategh3Date:2026/7/214Name:aroma.cpp5You steal,I kill.6*/7#include <cstdio>8#include <algorithm>9using namespace std;10#define MAXN 20001011struct item{12    int Val,Limit;13}Line[MAXN];14bool cmp(item a,item b){return a.Val>b.Val;}15int n,q,Fa[MAXN],cnt=0,In1;16long long Ans[MAXN];17int Find(int x){return Fa[x]==x?x:Fa[x]=Find(Fa[x]);}18int main(){19    freopen("aroma.in","r",stdin);20    freopen("aroma.out","w",stdout);21    scanf("%d%d",&n,&q);22    for(int i=1;i<=n;i++) scanf("%d%d",&Line[i].Val,&Line[i].Limit);23    sort(Line+1,Line+n+1,cmp);24    for(int i=0;i<=n;i++) Fa[i]=i;25    for(int i=1;i<=n;i++){26        int Day=Find(min(Line[i].Limit,n));27        if(Day==0) continue;28        Fa[Day]=Find(Day-1);29        cnt++;30        Ans[cnt]=Ans[cnt-1]+Line[i].Val;31    }32    while(q-->0){33        scanf("%d",&In1);34        printf("%lld\n",Ans[min(In1,cnt)]);35    }36    return 0;37}