解题报告

我不会“简单题”.jpg。可以考虑从 $(a,b)$ 到 $(c,d)$ 的两种走法：先上再右 $A_a(c-a)+B_d(d-b)$ 以及先右再上 $B_b(d-b)+A_c(c-a)$ ，如果先上更好那么 ${B_d-B_b\over d-b}\le{A_c-A_a\over c-a}$ ，发现这是个斜率形式QAQ，所以每个地方的决策和之后的斜率有关。

因此我们可以求出 $A$ 和 $B$ 的凸包，然后比较每个位置的斜率，进行决策就行了。

示例程序

#include<cstdio>
#include<cctype>
using namespace std;
typedef long long LL;
const int maxn=500000;

int n,m,a[maxn+5],b[maxn+5],A[maxn+5],B[maxn+5],PA[maxn+5],PB[maxn+5];LL ans;

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> inline int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    return lst=='-'?x=-tot:x=tot,Eoln(ch);
}
#define cmp(i,j,k) ((LL)(a[i]-a[k])*((i)-(j))<(LL)(a[i]-a[j])*((i)-(k)))
inline void Make(int *a,int *A,int *PA,int n){
    for (int i=1;i<=n;i++) {while (A[0]>1&&cmp(A[A[0]-1],A[A[0]],i)) A[0]--;A[++A[0]]=i;}
    for (int i=1,j=1;i<=n;i++) {while (j<=A[0]&&A[j]<=i) j++;PA[i]=j-1;}
}
inline bool check(int i,int j){
    if (i==A[0]) return true;if (j==B[0]) return false;
    return (LL)(b[B[j+1]]-b[B[j]])*(A[i+1]-A[i])<=(LL)(a[A[i+1]]-a[A[i]])*(B[j+1]-B[j]);
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    readi(n);readi(m);n++;m++;for (int i=1;i<=n;i++) readi(a[i]);for (int i=1;i<=m;i++) readi(b[i]);
    Make(a,A,PA,n);Make(b,B,PB,m);
    for (int i=1,j=1;i<n||j<m;) check(PA[i],PB[j])?(ans+=a[i],j++):(ans+=b[j],i++);
    printf("%lld\n",ans);return 0;
}