P8769-题解
_zuoqingyuan
·
·
题解
题面
传送门。
题意简述：有 n 种巧克力，第 i 种巧克力的单价是 a_i，这种巧克力可以在第 b_i 天前吃（包括 b_i 天，天数从 1 开始计）。这种巧克力一共有 c_i 块，买完就没有了。试问如何买巧克力，使得前 x 天每天都能吃巧克力，且方案价钱最小。若存在合法方案输出方案的价钱，如果不存在这样的方案，输出 -1。
分析：
可以把吃巧克力的过程这样看，小蓝一天买一个合法巧克力，将其吃掉。最后花掉的总价钱就是答案；如果某一天小蓝没有买到巧克力，说明无可行方案，直接输出 -1。
有一个很简单的贪心策略，我们我们可以把每一种巧克力放在一起，从前到后枚举每一天。找出这一堆巧克力中最便宜的一种，如果这种巧克力保质期已经超过了当前天数，或这种巧克力已经买了 c_i 次。就将它从这堆巧克力中扔出去。因为以后几天中这种巧克力都不是合法的，不会再对答案产生贡献。如果在找的过程中，这一天所有的巧克力都不合法，就说明这一天买不到巧克力，输出 -1。否则另答案累加上一个 a_i，标记买这种巧克力的次数加一重复这个过程，直到模拟了 x 天，输出答案。
但其实这种贪心策略并不正确，观察下面数据。
input:
3 3
1 3 2
5 1 1
100 3 5
output:7
wrong output:102
在这里正确的取法是先取 1 个第 2 种，两个第 1 种，价钱为 7。
那我们的策略如何选择呢？
$\mathrm{Day2}$ ：取出一个第 $1$ 种。
$\mathrm{Day3}$ ：第 $1$ 种被取完，第 $2$ 种过期，取出一个第 $3$ 种。
价钱和：$1+1+100=102$。
发现问题了吗？对于第 $1$ 种，我们如果在第 $1,2$ 天取它，那么第 $2$ 种就会过期；但如果我们在第 $2,3$ 天取它，那么我们还可以在第 $1$ 天取第 $2$ 种。
因此，在第几天买某一种巧克力也会影响答案，我们就要转变贪心策略。对于一种巧克力，能更晚买它就更晚买它，例如上面，对于第 $1$ 种巧克力，我们应在第 $2,3$ 天购买而不是第 $1,2$ 天购买。
# 做法一：二叉堆
## 实现：
观察上述的思路，我们需要在某一时刻把若干种巧克力放入一个数据结构，要求能取出当前价格最小巧克力以及删除不合法的巧克力，操作的时间复杂度均在 $O(\log n)$，以内。其实 STL 中的优先队列（也就是二叉堆）就能满足其操作。
代码实现很简单，期初堆为空，从第 $x$ 天开始倒退；如果在第 $k$ 天开始，有某几种巧克力的过期日期 $b_i\ge k$，就将这几种巧克力入堆。然后进行和上面同样的操作。就能完美解决问题了。
## Code：
十年 OI 一场空，_______ 。
```cpp
#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N=1e5+10;
struct node{
ll a,b,c;
}v[N];
bool operator < (const node u,const node v){
return u.a>v.a;
}//重载小于号
bool cmp(node a,node b){
return a.b>b.b;
}//排序函数
priority_queue<node>q;
ll n,x,ans,it=1,l=114514;
int main(){
scanf("%lld %lld",&x,&n);
for(int i=l;i<=n;i++){
node t;
scanf("%lld %lld %lld",&t.a,&t.b,&t.c);
v[i]=t;
}
sort(v+l,v+l+n,cmp);
for(int day=x;day>=1;day--){
while(it<=n&&v[it].b>=day)q.push(v[it]),it++;//把没入堆的push进去
while(q.size()&&q.top().c==0)q.pop();//删除堆顶不合法巧克力
if(!q.size()){
printf("-1\n");//判断无解情况
return 0;
}
node t=q.top();q.pop();
t.c--,ans+=t.a;
q.push(t);
}
printf("%lld\n",ans);
return 0;
}
```
[AC记录。](https://www.luogu.com.cn/record/142213700)
# 做法二：并查集
## 实现：
先将每组每种巧克力按照价格排序，然后轮流判断这种巧克力会在那几天吃。
按照上述的思路，假设我们要找到我们会在第几天吃第 $k$ 种巧克力。朴素算法是：按照 $b_k,b_k-1,b_k-2\dots 1$ 的顺序去找，在找的过程中， $c_k$ 个没买巧克力的天数但没枚举到第 $1$ 天或枚举到第 如果已经找到了$1$ 天但还没 找到$c_k$ 个没买巧克力的天数，都是直接退出当前循环，时间复杂度 $O(n^2)$。
我们用可以用一个并查集 $f_i$ 表示当前第 $i$ 天及以前第一个没买巧克力的某一天。起初，每个日子 $i$ 自己是一个集合（$f_i=i$）。每当我们确定要在第 $t$ 天买巧克力，就将日子 $i$ 这个集合并入日子 $i-1$($f_i=f_{i-1}$)。每次直接转移即可，时间复杂度 $O(n\alpha(n))$，其中 $\alpha(n)$ 表示反阿克曼函数。
题目中一个对于并查集很恶习的坑点，由于 $b_i \le 10^9$，如果直接查找 $f_{b_i}$ 会越界，所以要特判边界，如果 $b_i > x$，就直接查找 $f_x$ 即可。
## Code:
~~其实不开 long long 也能过~~
```cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef int ll;
const int N=1e5+10;
inline int read(){
int r=0;char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')r=(r<<1)+(r<<3)+(ch^48),ch=getchar();
return r;
}
void write(int r){
if(r>9)write(r/10);
putchar(r%10+'0');
return;
}
struct node{
ll a,b,c;
}v[N];
bool cmp(node a,node b){
return a.a<b.a;
}
ll n,x,ans,f[N],l=114514;
ll found(ll t){
if(t>x)return found(x);
return f[t]==t?t:f[t]=found(f[t]);
}
int main(){
x=read(),n=read();
for(int i=1;i<=n;i++){
v[i].a=read(),v[i].b=read(),v[i].c=read();
}
sort(v+1,v+1+n,cmp);
for(int i=1;i<=x;i++)f[i]=i;
for(int i=1;i<=n;i++){
for(int j=found(v[i].b);v[i].c&&j!=0;j=found(j-1))
ans+=v[i].a,v[i].c--,f[j]=found(f[j-1]);
}
for(int i=l;i<=x;i++){
if(f[i]==i){
write(-1);
return 0;
}
}
write(ans);
return 0;
}
```
历经艰苦卓绝的卡常，把时间卡到了 rk2 !!!
[AC记录。](https://www.luogu.com.cn/record/142621976)
如有错误，请指出。
## 后话
2024 的第一篇题解！
快期末考试，最近一段时间就不碰信奥了。