F. 买蛋糕 [ Problem 4833 ] [ Discussion ]
Description
RB买了个大蛋糕结果发现还是不够吃……
因为蛋糕不够吃，所以RB只能再去麦都买一些小蛋糕来分给朋友吃，RB的每个朋友都有一个吃蛋糕的最小体积要求，即小于这个体积的蛋糕那个朋友就不吃，即对于朋友ii，蛋糕的最小体积要求为ai,若第jj块蛋糕的体积vj<ai，则朋友ii就不吃蛋糕jj，RB急匆匆的赶到麦都，结果发现麦都的蛋糕不多了，只剩下柜台里的一些蛋糕
RB想知道，他应该买哪些蛋糕，才能让朋友都吃到蛋糕，且购买的蛋糕的总体积最小？
ps：如果怎么买都有朋友吃不到蛋糕，那RB就只能回去QAQ一下卖个萌了……
Input
输入包含多组数据，每组数据第一行有两个正整数n,m，第二行有nn个正整数，分别代表每个朋友的最小蛋糕体积要求，第三行有m个整数，分别代表麦都柜台里剩余的蛋糕的体积。**输入以n=0n=0且m=0结束**
Output
对于每组数据，输出最小体积，如果无解，输出QAQ。
Samples
Input Copy
8 13 1 28 18 25 24 7 25 11 18 9 48 44 29 50 40 24 17 25 21 12 22 12 13 14 24 4 17 27 23 27 18 28 21 20 21 19 43 21 12 36 47 15 14 43 40 10 5 23 0 0
Output
174 QAQ
Hint
- 对于前40%的数据，n,m≤20
- 对于前60%的数据，n,m≤100
- 对于前70%的数据，n,m≤1e5，且只有1组测试数据。
- 对于100%的数据，n,m≤1e6，有3至5组测试数据。
由于输入的数据量较大，请使用速度较快的读入方式。
题意就是每个小朋友都拿比自己a[i]大的b[i]问你拿完之后，ans最小是多少
这个要提的就是如何返回set中最后一个元素*st.rbegin()
#pragma GCC optimize(1) #pragma GCC optimize(2) #pragma GCC optimize(3,"Ofast","inline") #include<iostream> #include<set> #include<stdio.h> #include<algorithm> #include<cstring> /* 二分+set; 就是要判断序列的最后一个元素 */ using namespace std; typedef long long ll; template <typename Tp> void read(Tp &x){//read(n); x=0;char ch=1;int fh; while(ch!='-'&&(ch>'9'||ch<'0')){ ch=getchar(); } if(ch=='-'){ fh=-1;ch=getchar(); }else fh=1; while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+ch-'0';ch=getchar(); } x*=fh; } const int maxn=5e6+100; const int mod=1991; int n,m; ll a[maxn]; multiset<ll>st; int main(){ while(scanf("%d%d",&n,&m)){ if(n+m==0){ break; } for(register int i=1;i<=n;i++){ read(a[i]); } ll x; for(register int j=1;j<=m;j++){ read(x); st.insert(x); } sort(a+1,a+n+1); ll ans=0; int flag=1; for(register int i=1;i<=n;i++){ if(st.empty()||*st.rbegin()<a[i]){//返回set最后一个元素 flag=0; break; } else{ multiset <ll>::iterator z=st.lower_bound(a[i]); ans+=*z; st.erase(z); } } if(flag){ printf("%lld ",ans); } else{ printf("QAQ "); } st.clear(); } }