当前位置：首页 > news >正文

打卡信奥刷题（3439）用C++实现信奥题 P10334 [UESTCPC 2024] 饮料

news 2026/7/13 0:16:19

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

输入输出样例 #2

输入 #2

5 1 3 4 5 5 3 8 2 7 4

输出 #2

说明/提示

样例一解释如下：

时间	制作	取走
1 11	3 33	3 33
2 22	− -−	− -−
3 33	8 88	8 88
4 44	2 22	2 22
5 55	4 44	− -−
6 66	7 77	7 , 4 7,47,4

样例二解释如下：

时间	制作	取走
1 11	3 33	3 33
2 22	4 44	− -−
3 33	8 88	8 88
4 44	4 44	4 44
5 55	7 77	7 , 4 7,47,4
6 66	− -−	− -−

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;}