UESTC_1558
如果这个题目不考虑t而是改成问最少的转换次数，那么我们只要每次让它转换得越大越好，因此就可以将所有的exchange按r进行排序，每一次在一定的范围内选出v最大的exchange即可（这一点可以用堆来实现）。
而现在是需要考虑t的，显然就不能直接贪心了，于是我们不妨往dp的角度上想一下。如果dp的话，那么就涉及到一个顺序的问题，按我们上面的思路将r排序后进行dp是否可行呢？是可以的，不妨假设y.r>=x.r且 y能够更新x，而由于y.r>=x.r，那么更新y的那个点就一定也可以更新x，而这样是比用y去更新x更优的。因此，如果我们将exchange按r排序后，后面的点是不会作为更新前面的点的决策的。
接下来还有一个问题，就是我们如何去选择决策点呢，也就是说对于当前这个点i，我们选择前面的哪个点j来更新i？显然f[j]（用到第j个exchange时花费的最小时间）越小越好，但前面拥有最小的f[j]的这个点j是否一定符合要求呢？不一定，因为有可能j.v<i.r。这样我们再联想到选择最小的f[j]是用堆（这里我是用线段树实现的堆）来实现的，那么如果j.v<i.r我们就将其从堆中删除，直到遇到j.v>=i.r的j，这样是否可以呢？其实究竟可不可以是取决于我们当前删除的j还是否可能做为更新后续一些比i大的点的决策，这显然是不会的，因为我们是按r将点排序的，如果j.v<i.r，那么j.v一定小于后续所有点的r。
这样用线段树+dp的这个算法的可行性就讨论完了，最后再顺便说一下，我一开始写的时候结构体排序使用的是qsort，结果发现一直RE（只剩下了读入数据和排序的部分，其余部分全注释掉了），于是就想到不妨换一下sort试试，从队友那学完sort之后一交竟然真的AC了……难道这个题目对qsort有歧视……
#include<stdio.h> #include<string.h> #include<stdlib.h> #include<algorithm> #define MAXD 100010 #define INF 0x3f3f3f3f3f3f3f3fll using namespace std; int N, M, minf[4 * MAXD]; long long f[MAXD]; struct Ex { int v, r, t; bool operator < (const Ex &x) const { return r < x.r; } }ex[MAXD]; void update(int cur) { int ls = cur << 1, rs = cur << 1 | 1; minf[cur] = f[minf[ls]] < f[minf[rs]] ? minf[ls] : minf[rs]; } void build(int cur, int x, int y) { int mid = (x + y) >> 1, ls = cur << 1, rs = cur << 1 | 1; minf[cur] = 0; if(x == y) { f[x] = INF; return ; } build(ls, x, mid); build(rs, mid + 1, y); } void refresh(int cur, int x, int y, int k, int op) { int mid = (x + y) >> 1, ls = cur << 1, rs = cur << 1 | 1; if(x == y) { minf[cur] = (op ? k : 0); return ; } if(k <= mid) refresh(ls, x, mid, k, op); else refresh(rs, mid + 1, y, k, op); update(cur); } void init() { int i; scanf("%d%d", &N, &M); ++ N; ex[1].v = 1, ex[1].r = ex[1].t = 0; for(i = 2; i <= N; i ++) scanf("%d%d%d", &ex[i].v, &ex[i].r, &ex[i].t); sort(ex + 1, ex + 1 + N); build(1, 1, N); f[0] = INF, f[1] = 0; refresh(1, 1, N, 1, 1); } void solve() { int i, j, k; long long ans = INF; for(i = 2; i <= N; i ++) { while((k = minf[1]) && ex[k].v < ex[i].r) refresh(1, 1, N, k, 0); if(k == 0) break; f[i] = f[k] + ex[i].t; refresh(1, 1, N, i, 1); } for(i = 1; i <= N; i ++) if(ex[i].v >= M && f[i] < ans) ans = f[i]; printf("%lld\n", ans == INF ? -1ll : ans); } int main() { int t, tt; scanf("%d", &t); for(tt = 0; tt < t; tt ++) { init(); printf("Case #%d: ", tt + 1); solve(); } return 0; }