P10334 [UESTCPC 2024] 饮料

题目描述

有一个果汁机，每分钟可以制作一杯任意体积的果汁。

有n nn个人排成一队。第i ii个人将在第t i t_iti​分钟走到果汁机前，并拿走当前已经制作的果汁中体积最大的一杯。第i ii个人拿到体积大于等于a i a_iai​的果汁就会满意。如果此时没有果汁，则第i ii个人也会不满意。

问是否能够让所有人满意。如果是，输出让所有人满意所需的果汁体积之和的最小值。

输入格式

第一行一个整数n nn( 1 ≤ n ≤ 2 × 10 5 ) (1\leq n\leq 2 \times 10^5)(1≤n≤2×105)，表示队伍中人的数量。

接下来一行n nn个整数t 1 , t 2 , … , t n t_1,t_2,\ldots,t_nt1​,t2​,…,tn​( 1 ≤ t 1 ≤ t 2 ≤ … ≤ t n ≤ 10 9 ) (1\leq t_1\leq t_2\leq\ldots\leq t_n\leq 10^9)(1≤t1​≤t2​≤…≤tn​≤109)，其中t i t_iti​表示第i ii个人到果汁机前的时间。如果两个人的到达时间相同，则按题目给出的顺序从左到右决定先后。

接下来一行n nn个整数a 1 , a 2 , … , a n a_1,a_2,\ldots,a_na1​,a2​,…,an​( 1 ≤ a i ≤ 10 9 ) (1\leq a_i\leq 10^9)(1≤ai​≤109)，其中a i a_iai​表示第i ii个人对果汁的体积要求。

输出格式

如果不能令所有人满意，输出− 1 -1−1。

否则输出一行一个整数，表示所需的最小体积和。

输入输出样例 #1

输入 #1

5 1 3 4 6 6 3 8 2 7 4

输出 #1

24

输入输出样例 #2

输入 #2

5 1 3 4 5 5 3 8 2 7 4

输出 #2

26

说明/提示

样例一解释如下：

样例二解释如下：

C++实现

#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=200005;intn;intt[N],a[N],s[N],top;signedmain(){cin>>n;for(inti=1;i<=n;i++){cin>>t[i];if(i>t[i])returncout<<-1,0;}for(inti=1;i<=n;i++)cin>>a[i];s[++top]=a[n];intsum=a[n];for(inti=n-1;i>=1;i--){if(t[i]==t[i+1]){if(s[top]>=a[i]){intx=s[top];sum+=x;s[++top]=x;}else{sum+=a[i];s[++top]=a[i];}}else{for(intj=1;j<=t[i+1]-t[i];j++){if(top!=0)top--;elsebreak;}if(s[top]>=a[i]){intx=s[top];s[++top]=x;sum+=x;}else{s[++top]=a[i];sum+=a[i];}}}cout<<sum;return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容