首页 > 代码库 > 【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】旅行家的预算