这道题感觉挺吃力的，还用到了我不熟悉的优先队列
题目中的推导也都看明白了，总之以后还要多体会才是
这里用优先对列的原因就是因为要维护一个滑动区间的最小值，比如在区间里２在１的前面，２在离开这个滑动区间会一直被１给“压迫”着，所以这个２是无用的，应当及时删除。这样的话剩下的元素都是递增的，优先队列也称单调队列也因此得名。
先把代码贴上：
1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 using namespace std; 6 7 const int maxn = 100000 + 10; 8 int x[maxn], y[maxn]; 9 int total_dist[maxn], total_weight[maxn], dist2origin[maxn]; 10 int q[maxn], d[maxn]; 11 12 int func(int i) 13 { 14 return d[i] - total_dist[i+1] + dist2origin[i+1]; 15 } 16 17 int main(void) 18 { 19 #ifdef LOCAL 20 freopen("3983in.txt", "r", stdin); 21 #endif 22 23 int T; 24 scanf("%d", &T); 25 while(T--) 26 { 27 int c, n, w, front, rear; 28 scanf("%d%d", &c, &n); 29 total_dist[0] = total_weight[0] = x[0] = y[0] = 0; 30 for(int i = 1; i <= n; ++i) 31 { 32 scanf("%d%d%d", &x[i], &y[i], &w); 33 dist2origin[i] = x[i] + y[i]; 34 total_dist[i] = total_dist[i-1] + abs(x[i] - x[i-1]) + abs(y[i] - y[i-1]); 35 total_weight[i] = total_weight[i-1] + w; 36 } 37 front = rear = 1; 38 for(int i = 1; i <= n; ++i) 39 { 40 while(front <= rear && total_weight[i] - total_weight[q[front]] > c) 41 ++front; 42 d[i] = func(q[front]) + total_dist[i] + dist2origin[i]; 43 while(front <= rear && func(q[rear]) >= func(i)) 44 --rear; 45 q[++rear] = i; 46 } 47 printf("%d ", d[n]); 48 if(T) printf(" "); 49 } 50 return 0; 51 }