C++14(g++5.4) 解法, 执行用时: 1546ms, 内存消耗: 7372K, 提交时间: 2019-05-19 23:20:31

#include <bits/stdc++.h>
#define mp make_pair
#define pii pair<int,int>
using namespace std;
typedef long long ll;
#define rint register int
const int maxn=100007;
const int inf=(1LL<<29);
ll t[maxn],a[maxn],b[maxn];
struct point{
    int pos,c;ll t;
    point(int pos,ll t,int c):pos(pos),t(t),c(c){}
    bool operator < (point x) const{
        return 1LL*a[pos]*b[c]>1LL*a[x.pos]*b[x.c];
    }
};
int main(){
    //cin.tie(0);ios_base::sync_with_stdio(false);
    int n,c;long long w;cin>>n>>c>>w;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=c;i++) cin>>b[i];
    ll l=0,r=1e12;
    ll ans=-1;
    while(l<=r){
        int now=c;
        priority_queue<point> q;
        ll mid=(l+r)>>1;
        for(int i=1;i<=n;i++){
            t[i]=mid>=i?(mid-i)/n+1:0;
        }
        for(int i=1;i<=n;i++){
            if(t[i]) q.push(point(i,t[i],1));
        }
        ll z=w;
        while(now&&q.size()){
            point p=q.top();q.pop();p.t--;
            z-=1LL*a[p.pos]*b[p.c];
            if(!p.t) p.t=t[p.pos],p.c++;
            q.push(p);
            now--;
        }
        //cout<<z<<" "<<now<<endl;
        if(z>0&&!now) r=mid-1,ans=mid;
        else l=mid+1;
    }
    cout<<ans;
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 597ms, 内存消耗: 6988K, 提交时间: 2020-03-30 22:20:08

#include<bits/stdc++.h>
using namespace std;

struct node
{
	long long x,y,num;
	bool operator<(const node &a)const
	{
		return a.num<num; 
	} 
}r,f;
long long n,m,w,a[100005],b[100005];
priority_queue<node>q,Q;
bool judge(long long time)
{
	long long i,s=0,c=0;
	Q=q;
	while(!Q.empty())
	{
		f=Q.top(),Q.pop();
		i=time/n+(f.x<=time%n?1:0);
		if(!i)continue;
		if(m-c>=i)
		{
			c+=i,s+=f.num*i;
			if(f.y+1<=m)r.x=f.x,r.y=f.y+1,r.num=a[f.x]*b[f.y+1],Q.push(r);
		}
		else
		{
			s+=(m-c)*f.num;
			break;
		}
		if(s>=w)break;
	}
	if(s<w)return 1;
	return 0;
}
int main() 
{
    long long i,L,R,Mid,ans=-1;
	scanf("%lld%lld%lld",&n,&m,&w);
    for(i=1;i<=n;i++)scanf("%lld",&a[i]);
    for(i=1;i<=m;i++)scanf("%lld",&b[i]);
    for(i=1;i<=n;i++)r.x=i,r.y=1,r.num=a[i]*b[1],q.push(r);
    for(L=1,R=n*m;L<=R;)
	{
		Mid=(L+R)>>1;
		if(judge(Mid))ans=Mid,R=Mid-1;
		else L=Mid+1;
	}
	printf("%lld\n",ans);
    return 0;
}