AtCoder Beginner Contest 376（C，E题题解）

C - Prepare Another Box

题意：给你n个玩具，n-1个盒子，然后让你判断如果再加一个盒子，加的盒子最小的体积是多少，才能将其全部装下（一个盒子只能装1个玩具），让你判断时候能够让这n个盒子装下n个玩具

思路：我们现将玩具和盒子全部进行排序，我们去遍历盒子，用cnt去统计装不下的数量，然后我们倒序遍历，如果这个盒子能装下这个玩具，那么就判断下一个盒子和下一个玩具，如果碰到装不下的，那么就将cnt++，flag设置为当前玩具的体积大小，然后去判断有多少非法数量即可

不合格的数量是0，那么就说明我们再找一个盒子装最小的那个玩具即可，如果为1，那么就输出flag的值，如果大于1，那么就是有多个都装不下，那么就是-1

#include<bits/stdc++.h>
using namespace std;
#define int long long
int t;
int n;
int a[200005];
int b[200005];
signed main()
{int flag=0;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=n-1;i++){cin>>b[i];}sort(a+1,a+1+n);sort(b+1,b+n);int pos=n;int cnt=0;for(int i=n-1;i>=1;i--){if(b[i]<a[pos]){i++;cnt++;flag=a[pos];}pos--;}if(cnt==0){cout<<a[1]<<"\n";}else if(cnt==1){cout<<flag<<"\n";}elsecout<<-1<<"\n";return 0;
}

E - Max × Sum

我们要求的是a数组的最值*b数组的和，我们考虑是否能够先固定下来一部分，经过分析我们可以发现，我们可以将整个区间的最值先确定下来，对数组进行排序(当然了，a数组变了，我们的b数组也要跟着变，可以考虑用结构体或者pair<int,int>)，然后我们每当遍历到一个新的点，我们只需要去维护前面k-1个最小的值即可，我们可以考虑用最大堆(优先队列)去实现，然后当队列里面的值大于k-1个就直接弹出最上面的值( top() ) 

#include<bits/stdc++.h>
using namespace std;
#define int long long
int t;
int n,k;
struct node{int a;int b;
};
bool cmp(node x, node y)  
{  return x.a < y.a;   
}
void solve()
{priority_queue<int> q;int minn=2e18;cin>>n>>k;vector<node> c(n+1);for(int i=1;i<=n;i++){cin>>c[i].a;}for(int i=1;i<=n;i++){cin>>c[i].b;}sort(c.begin()+1,c.end(),cmp);int sum=0;for(int i=1;i<=k-1;i++){q.push(c[i].b);sum+=c[i].b;}for(int i=k;i<=n;i++){if(q.size()==k){sum-=q.top();q.pop();}q.push(c[i].b);sum+=c[i].b;minn=min(minn,c[i].a*sum);}cout<<minn<<"\n";return;
}
signed main()
{cin>>t;while(t--)solve();return 0;
}