P4531题解
Point_Nine
·
·
题解
考虑两个比较好想贪心。
$ 2. $ 两个比较大小接近的放在一起比较优 。
现将原数组排序。
手玩几组样例发现,为了满足贪心原则 $ 1 , 2 $ ，最后的答案肯定是从 $ 1 $ 开始的连续一段。
可以考虑枚举连续一段的端点,判定是否合法即可。
复杂度 $ O(n^2) $ ，实际远远达不到。
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int rd(){
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
vector<int> s1,s2;
int Ans_cnt,Now_s;
int n,m,s,num;
signed main()
{
// s1.resize(55000);
// s2.resize(55000);
// freopen("7.in","r",stdin);
// freopen("Ans.out","w",stdout);
n=rd();
m=rd();
s=rd();
for(int i=1;i<=n;i++)
{
int a;
a=rd();
s1.push_back(a);
}
for(int i=1;i<=m;i++)
{
int a;
a=rd();
s2.push_back(a);
}
if(s1.size()<s2.size()) s1.swap(s2);
sort(s1.begin(),s1.end());
sort(s2.begin(),s2.end());
int sum=0;
for(vector<int>::iterator it=s1.begin();it!=s1.end();it++)
{
int cnt=num;
int Maxn=0,xuan;
if(it==s1.end()) continue;
vector<int>::iterator it1=it;
vector<int>::iterator it2=s2.begin();
int now_sum=sum;
while(1)
{
Maxn=max(*it1,*it2);
if((now_sum+Maxn)*Maxn>s) break;
xuan=Maxn;
now_sum+=Maxn;
cnt+=2;
it1++;
it2++;
if(it1==s1.end()||it2==s2.end()) break;
}
if(cnt>Ans_cnt)
{
Now_s=xuan*now_sum;
Ans_cnt=cnt;
}
else if(cnt==Ans_cnt)
{
Now_s=min(Now_s,xuan*now_sum);
}
sum+=*it;
num++;
if(sum*Maxn>s||it1==s1.end()) break;
}
cout<<Ans_cnt<<" "<<Now_s<<endl;
}
```