贪心。当前位置满油可达的gas station中，如果有比它小的，则加油至第一个比他小的。没有，则加满油，先到达这些station中最小的。注意数的范围即可。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL long long using namespace std; const int MAXN = 200050; int d, n, m; int gp[MAXN], gpz[MAXN];
int fl[MAXN]; struct gas{
int pos, price;
}g[MAXN]; bool cmp(gas a, gas b){
if(a.pos < b.pos) return true;
return false;
} int main(){
scanf("%d%d%d", &d, &n, &m); gp[0] = 0, gpz[0] = 1e7;
for(int i = 1; i <= m; i++){
scanf("%d%d", &g[i].pos, &g[i].price);
} sort(g + 1, g + 1 + m, cmp); for(int i = 1; i <= m; i++){
gp[i] = g[i].pos, gpz[i] = g[i].price;
} gp[m + 1] = d, gpz[m + 1] = 0; /*
for(int i = 0; i<= m + 1; i++)
cout <<gp[i] <<" "<< gpz[i] << endl;
cout << endl;
*/
int mindist = -1; for(int i = 0; i <= m; i++){
mindist = max(mindist, gp[i + 1] - gp[i]);
} // cout << mindist << endl; if(mindist > n){
puts("-1");
return 0;
} if(d <= n){
puts("0");
return 0;
} for(int i = m; i >= 0; i--){
if(gpz[i + 1] <= gpz[i]){
fl[i] = i + 1;
}
else {
int tmp = i + 1;
while(gpz[fl[tmp]] > gpz[i]){
tmp = fl[tmp];
}
fl[i] = fl[tmp];
}
}
/*
for(int i = 0; i<= m; i++){
cout << fl[i] <<" ";
}
cout << endl; */ LL ans = 0;
int liter = n; for(int l = 0; l < m+ 1; ){
if(gp[fl[l]] - gp[l] > n){
ans += (LL)(n - liter) * gpz[l];
int tmp = l + 1;
while(gp[fl[tmp]] - gp[l] <= n){
tmp = fl[tmp];
}
liter = n - (gp[tmp] - gp[l]);
l = tmp;
}
else{
int tmp = fl[l];
if(tmp == m + 1){
ans += (LL)(d - gp[l] - liter) * gpz[l];
break;
}
else{
if(gp[tmp] - gp[l] <= liter){
liter -= gp[tmp] - gp[l];
}
else{
ans += (LL)(gp[tmp] - gp[l] - liter)*gpz[l];
liter = 0;
}
l = tmp;
}
}
// cout << l << endl;
// system("pause");
}
cout << ans << endl; }