滑动窗口

#include <stdio.h>
#include <stdlib.h>typedef struct {long long p;  // 怪物位置int c;        // 怪物积分
} Monster;int main() {int T;scanf("%d", &T);while (T--) {int n;long long m;scanf("%d %lld", &n, &m);Monster *monsters = (Monster*)malloc(n * sizeof(Monster));for (int i = 0; i < n; i++) {scanf("%lld %d", &monsters[i].p, &monsters[i].c);}// 题目已说明p单调不减，无需排序// qsort(monsters, n, sizeof(Monster), cmp);long long sum = 0;long long max_sum = 0;int left = 0;// 滑动窗口：right为右端点，left为左端点for (int right = 0; right < n; right++) {sum += monsters[right].c;// 若当前区间长度超过能量m，移动左端点while (monsters[right].p - monsters[left].p > 2*m) {sum -= monsters[left].c;left++;}// 更新最大积分if (sum > max_sum) {max_sum = sum;}}printf("%lld\n", max_sum);free(monsters);}return 0;
}