首页 > 代码库 > 【NOIP1999】【Codevs 1046】旅行家的预算
【NOIP1999】【Codevs 1046】旅行家的预算
http://codevs.cn/problem/1046/
Solution:
贪心,如果当前油价很低,它就比起当前剩余油的价还低就可以替换,并且每次加满,最后把剩的油卖掉即可
油价用单调链表(不知到为什么会写链表,脑抽,当时觉得插入方便,其实不用插入。。。尴尬)维护 or 堆(你也可以脑抽,加个log),没事啦,数据水
// <travel.cpp> - 06/23/16 12:55:15// This file is made by YJinpeng,created by XuYike‘s black technology automatically.// Copyright (C) 2016 ChangJun High School, Inc.// I don‘t know what this program is.#include <iostream>#include <vector>#include <algorithm>#include <cstring>#include <cstdio>#include <cstdlib>#include <cmath>#define MOD 1000000007#define INF 1e9using namespace std;typedef long long LL;const int MAXN=100010;const int MAXM=100010;inline int max(int &x,int &y) {return x>y?x:y;}inline int min(int &x,int &y) {return x<y?x:y;}inline int getint() { register int w=0,q=0;register char ch=getchar(); while((ch<‘0‘||ch>‘9‘)&&ch!=‘-‘)ch=getchar(); if(ch==‘-‘)q=1,ch=getchar(); while(ch>=‘0‘&&ch<=‘9‘)w=w*10+ch-‘0‘,ch=getchar(); return q?-w:w;}struct Edge{ double p,q; Edge* next;};double d[MAXN],c[MAXN],D,C,V,w[MAXN],ans,k;int n;int main(){ freopen("travel.in","r",stdin); freopen("travel.out","w",stdout); scanf("%lf %lf %lf %lf",&D,&C,&V,&w[1]); n=getint()+1; for(int i=2;i<=n;i++)scanf("%lf %lf",&d[i],&w[i]); d[n+1]=D; for(int i=1;i<=n;i++)c[i]=(d[i+1]-d[i])/V; Edge* root=new Edge; Edge* now;Edge* the; ans=0;c[0]=C;root->next=NULL; for(int i=1;i<=n;i++){ if(c[i]>C){printf("No Solution");return 0;} now=root; while(now->next!=NULL){the=now->next;if(the->q>w[i])break;now=now->next;} k=c[i-1];the=now; while(the->next)the=the->next,k+=the->p,ans-=the->p*the->q; the=new Edge; the->next=NULL; the->p=k;the->q=w[i]; now->next=the;now=root->next; ans+=k*w[i]; k=c[i]; while(k>0){ if(k<now->p){now->p-=k;break;} k-=now->p; now=now->next; } root->next=now; } while(root->next){root=root->next;ans-=root->p*root->q;} printf("%.2lf",ans); return 0;}
【NOIP1999】【Codevs 1046】旅行家的预算
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。