题解 | #十字斩-研发#
配方制作-研发
http://www.nowcoder.com/questionTerminal/4f683379ce5740adb69c9ccacd9c9e97
递归
#include<bits/stdc++.h> using namespace std; struct node { int t,id,w; }a[100005]; int k; int sum[100005]; int temp; int dfs(int l) { int r = l+1; while(a[l].id != a[r].id) { sum[l] += dfs(r); r = temp; } sum[l] = (a[r].t - a[l].t) - sum[l]; temp = r+1; return a[r].t - a[l].t; } int main() { int t,n; cin >> t; while(t--) { cin >> n; for(int i = 1; i <= n; i++) { cin >> a[i].t >> a[i].id >> a[i].w; } dfs(0); int maxn = 0; int id = 0; for(int i = 1; i <= n; i++) { if(maxn < sum[i]) { maxn = sum[i]; id = a[i].id; } else if(maxn == sum[i] && id > a[i].id) { id = a[i].id; } sum[i] = 0; a[i].id = 0;//不清零会发生段错误 } sum[0] = 0; sum[n+1] = 0; cout << id << "\n"; } }