题解 P4266 【[USACO18FEB]Rest Stops】

Anfangen · 2018-11-30 09:59:43 · 题解

此题可以优化到O(N)

在O(N\log N)算法中，排序的目的是求出一个价值递减的序列，以保证当前所选的是当前最优解。

既然我们不必在乎其他不是最优解的价值，排序没有必要。

只须先逆序扫一遍所有的休息站，找出在每一阶段的最优解，将其记录在一个数组中，在第二遍扫的时候，算出价值即可。

49ms，luogu 1st。

#include <cstdio>
#include <iostream>
#include <cctype>
#include <cstring>
#include <map>
#include <stack>
#include <utility>
#include <string>
#include <algorithm>
#define gc() getchar()
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dec(i,a,b) for(int i=(a);i>=(b);--i)
#define endll putchar('\n');
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int  MAXOUT=10000;
const int MAXBUF=10000;
char buf[MAXBUF],*ps=buf,*pe=buf+1;
inline void rnext(){
    if(++ps == pe)
        pe = (ps = buf)+fread(buf,sizeof(char),sizeof(buf)/sizeof(char),stdin);
}
inline bool in(ll &ans){
    ans = 0;
    ll f = 1;
    if(ps == pe) return false;//EOF
    do{
        rnext();
        if('-' == *ps) f = -1;
    }while(!isdigit(*ps) && ps != pe);
    if(ps == pe) return false;//EOF
    do{
        ans = (ans<<1)+(ans<<3)+*ps-48;
        rnext();
    }while(isdigit(*ps) && ps != pe);
    ans *= f;
    return true;
}
char bufout[MAXOUT], outtmp[50],*pout = bufout, *pend = bufout+MAXOUT;
inline void write(){
    fwrite(bufout,sizeof(char),pout-bufout,stdout);
    pout = bufout;
}
inline void out_char(char c){ *(pout++) = c;if(pout == pend) write();}
inline void out_str(char *s){
    while(*s){
        *(pout++) = *(s++);
        if(pout == pend) write();
    }
}
inline void out_int(ll x) {
    if(!x){
        out_char('0');
        return;
    }
    if(x < 0) x = -x,out_char('-');
    int len = 0;
    while(x){
        outtmp[len++] = x%10+48;
        x /= 10;
    }
    outtmp[len] = 0;
    for(int i = 0, j = len-1; i < j; i++,j--) swap(outtmp[i],outtmp[j]);
    out_str(outtmp);
}
inline void out_int_ln(ll k){
    out_int(k);
    out_char('\n');
}
const int maxn=101101;
ll l,n,rf,rb;
struct kusa{
    ll dis,val;
    kusa(){}
    kusa(ll _dis,ll _val){dis=_dis;val=_val;}
}k[maxn];
bool operator <(const kusa &a,const kusa &b){
    if(a.val==b.val) return a.dis>b.dis;
    return a.val>b.val;
}
ll ans;
ll tmp_max;
bool decmax[maxn];
int tmp_dis=0;
int main(){
    in(l),in(n),in(rf),in(rb);
    rep(i,1,n) in(k[i].dis),in(k[i].val);
    dec(i,n,1)
        if(k[i].val>tmp_max) decmax[i]=true,tmp_max=k[i].val;
    rep(i,1,n)
        if(decmax[i]==true){
            ans+=k[i].val*(rf-rb)*(k[i].dis-tmp_dis);
            tmp_dis=k[i].dis;
        }
    out_int_ln(ans);
    write();
    return 0;
}