题解：CF1218F Workout plan

leo120306 · 2024-06-18 18:01:51 · 题解

题目翻译

翻译

都是我自己手翻的，应该比机翻好一点吧，如果有什么问题还请指教。

思路

贪心即可。能不买饮料就不买饮料，如果第 i 天一定要买，找到第 i 天及以前没买过饮料的店中最便宜的一家买饮料，直到超过第 i 天的目标。如果之前所有店都买过了，就是无解。此算法的正确性可以感性理解。

这个过程可以使用小根堆来优化。发现其他题解都是优先队列，那我就手写堆吧。

代码及细节

• 考虑到极限情况下，答案 =\sum C_i\leq 10^{14}，所以答案要开 long long。
• 手写堆不要打错了，（个人认为）比某区间数据结构还难调。

  
  #include <cstdio>
  using namespace std;

char chrd;

define read(x){ \

x=0;\
chrd=getchar();\
while(chrd<'0'||chrd>'9') chrd=getchar();\
while(chrd>='0'&&chrd<='9'){\
    x=(x<<3)+(x<<1)+(chrd^48);\
    chrd=getchar();\
}\

} int tsw;

define swap(x,y){tsw=x;x=y;y=tsw;}

// 以上是一些宏定义

int h[100005],sizh; inline void add(int x){ h[++sizh]=x; int now=sizh; while(now){ if(h[now>>1]>h[now])swap(h[now],h[now>>1]) else break; now>>=1; } }

inline void pop(){ swap(h[sizh],h[1]);sizh--; int now=1; while((now<<1)<=sizh){ int son=now<<1; if(son+1<=sizh&&h[son+1]<h[son])son++; if(h[son]<h[now])swap(h[now],h[son]) else break; now=son; } }

// 以上是堆

int x[100005],c[100005];

int main(){ int n,k,a; read(n);read(k); for(int i=1;i<=n;i++) read(x[i]); read(a); for(int i=1;i<=n;i++) read(c[i]); long long sum=0; for(int i=1;i<=n;i++){ add(c[i]); while(k<x[i]){ if(sizh==0){ printf("-1\n"); return 0; } k+=a; sum+=h[1]; pop(); } } printf("%lld",sum); return 0; }