1 条题解

  • 0
    @ 2022-6-12 10:30:40
    #include<bits/stdc++.h>
    using namespace std;
    double maxdis,c,dis;
    double minp=0,len=0;
    int n=0,k=0,f=0;
    struct node
    {
    	double d,p;
    }t[10];
    void dfs(int x)
    {
    	int li=x;
    	double lp=999.0;
    	k=0;
    	if(x==n)
    	{
    		if((maxdis-t[x].d-len)/dis>c)
    		{
    			f=1;
    			return;
    		}
    		minp+=(maxdis-t[x].d-len)/dis*t[x].p;
    		return;
    	}
    	for(int i=x+1;i<=n;i++)
    	{
    		if(t[x].d+c*dis>=t[i].d)
    		{
    			k=1;
    			if(t[i].p<=lp)
    			{
    				lp=min(lp,t[i].p);
    				li=i;
    			}
    		}
    	}
    	if(k==0)
    	{
    		f=1;
    		return;
    	}
    	if(t[x].p<t[li].p&&t[x].d+c*dis>=maxdis)
    	{
    		minp+=(maxdis-t[x].d-len)/dis*t[x].p;
    		return;
    	}
    	if(t[x].p<t[li].p)
    	{
    		len=0;
    		minp+=c*t[x].p;
    		len=c*dis-(t[li].d-t[x].d);
    	}
    	else minp+=(t[li].d-t[x].d-len)/dis*t[x].p;
    	dfs(li);
    	return;
    }
    bool cmp(node x,node y)
    {
    	return x.d<y.d;
    }
    int main()
    {
    	
    	cin>>maxdis>>c>>dis>>t[0].p>>n;
    	t[0].d=0;
    	for(int i=1;i<=n;i++)
    		cin>>t[i].d>>t[i].p;
    	if(n==0)
    	{
    		if((maxdis-t[0].d)/dis>c)
    		{
    			cout<<"No Solution\n";
    			return 0;
    		}
    		minp+=(maxdis-t[0].d)/dis*t[0].p;
    		printf("%.2lf\n",minp);
    		return 0;
    	}
    	sort(t+1,t+n+1,cmp);
    	dfs(0);
    	if(f==0)	printf("%.2lf\n",minp);
    	else cout<<"No Solution";
    	return 0;
    }
    
    
    • 1

    信息

    ID
    17
    时间
    1000ms
    内存
    128MiB
    难度
    4
    标签
    递交数
    9
    已通过
    4
    上传者