3 条题解

  • 1
    @ 2024-4-21 18:31:19
    #include <bits/stdc++.h>
    using namespace std;
    #define maxn 100000
    #define db double
    #define INF 9999999 
    int n;
    db D1,D2,C,P,res,ans,maxx;
    struct node
    {
    	db co,dis;
    	bool friend operator<(const node&a,const node&b){return a.dis<b.dis;}
    }pl[maxn];
    
    int Solve(int now)
    {
    	int flag=INF;db d=pl[now].dis; 
    	for(int i = now + 1; i <= n && pl[i].dis - d <= maxx; i ++)
    	{
    		if(pl[i].co < pl[now].co)
    		{
    			ans += ((pl[i].dis - d - res) / D2) * pl[now].co;
    			res = 0; return i;
    		}
    		if(flag == INF || pl[i].co < pl[flag].co) flag = i;
    	}
    	if(D1 - pl[now].dis <= maxx)
    	{
    		ans += ((D1 - pl[now].dis - res) / D2) * pl[now].co;
    		return INF;
    	}
    	if(flag==INF)printf("No Solution\n");return -1;
    	else
    	{
    		ans+=C*pl[now].co; res+=(maxx-(pl[flag].dis-d));
    		return flag;
    	}
    }
    
    int main()
    {
    	scanf("%lf%lf%lf%lf%d",&D1,&C,&D2,&P, &n);
    	pl[0].dis = 0, pl[0].co = P;
    	for(int i = 1; i <= n; i ++) 
    		scanf("%lf%lf", &pl[i].dis, &pl[i].co);
    	sort(pl, pl + n + 1);
    	maxx = C * D2;
    	int k = 0, t;
    	do
    	{
    		t = Solve(k), k = t;
    		if(t == -1) return 0;
    	}while(t != INF);
    	printf("%.2lf", ans);
    	return 0;
    }
    
    • 1
      @ 2024-4-12 19:27:59
      #include <bits/stdc++.h>
      using namespace std;
      #define maxn 100000
      #define db double
      #define INF 9999999 
      int n;
      db D1, D2, C, P, res, ans, maxx;
      
      struct node
      {
      	db co, dis;
      	bool friend operator <(const node& a, const node& b)
      	{ return a.dis < b.dis; }
      }pl[maxn];
      
      int Solve(int now)
      {
      	int flag = INF; db d = pl[now].dis; 
      	for(int i = now + 1; i <= n && pl[i].dis - d <= maxx; i ++)
      	{
      		if(pl[i].co < pl[now].co)
      		{
      			ans += ((pl[i].dis - d - res) / D2) * pl[now].co;
      			res = 0; return i;
      		}
      		if(flag == INF || pl[i].co < pl[flag].co) flag = i;
      	}
      	if(D1 - pl[now].dis <= maxx)
      	{
      		ans += ((D1 - pl[now].dis - res) / D2) * pl[now].co;
      		return INF;
      	}
      	if(flag == INF) { printf("No Solution\n"); return -1; }
      	else
      	{
      		ans += C * pl[now].co; res += (maxx - (pl[flag].dis - d));
      		return flag;
      	}
      }
      
      int main()
      {
      	scanf("%lf%lf%lf%lf%d", &D1, &C, &D2, &P, &n);
      	pl[0].dis = 0, pl[0].co = P;
      	for(int i = 1; i <= n; i ++) 
      		scanf("%lf%lf", &pl[i].dis, &pl[i].co);
      	sort(pl, pl + n + 1);
      	maxx = C * D2;
      	int k = 0, t;
      	do
      	{
      		t = Solve(k), k = t;
      		if(t == -1) return 0;
      	}while(t != INF);
      	printf("%.2lf", ans);
      	return 0;
      }
      
      • 0
        @ 2023-4-30 12:51:15
        #include <bits/stdc++.h>
        using namespace std;
        #define maxn 100000
        #define db double
        #define INF 9999999 
        int n;
        db D1, D2, C, P, res, ans, maxx;
        
        struct node
        {
        	db co, dis;
        	bool friend operator <(const node& a, const node& b)
        	{ return a.dis < b.dis; }
        }pl[maxn];
        
        int Solve(int now)
        {
        	int flag = INF; db d = pl[now].dis; 
        	for(int i = now + 1; i <= n && pl[i].dis - d <= maxx; i ++)
        	{
        		if(pl[i].co < pl[now].co)
        		{
        			ans += ((pl[i].dis - d - res) / D2) * pl[now].co;
        			res = 0; return i;
        		}
        		if(flag == INF || pl[i].co < pl[flag].co) flag = i;
        	}
        	if(D1 - pl[now].dis <= maxx)
        	{
        		ans += ((D1 - pl[now].dis - res) / D2) * pl[now].co;
        		return INF;
        	}
        	if(flag == INF) { printf("No Solution\n"); return -1; }
        	else
        	{
        		ans += C * pl[now].co; res += (maxx - (pl[flag].dis - d));
        		return flag;
        	}
        }
        
        int main()
        {
        	scanf("%lf%lf%lf%lf%d", &D1, &C, &D2, &P, &n);
        	pl[0].dis = 0, pl[0].co = P;
        	for(int i = 1; i <= n; i ++) 
        		scanf("%lf%lf", &pl[i].dis, &pl[i].co);
        	sort(pl, pl + n + 1);
        	maxx = C * D2;
        	int k = 0, t;
        	do
        	{
        		t = Solve(k), k = t;
        		if(t == -1) return 0;
        	}while(t != INF);
        	printf("%.2lf", ans);
        	return 0;
        }
        
        • @ 2023-8-15 21:02:38

          确定这是安全放心吃的AC还是吃了中毒的WA 嘻嘻

        • @ 2023-8-25 16:51:36

          @必定AC,不过不是核oj

      • 1

      [NOIP1999 普及/提高组] 旅行家的预算

      信息

      ID
      1756
      时间
      1000ms
      内存
      256MiB
      难度
      10
      标签
      递交数
      23
      已通过
      0
      上传者