javascript:(function(){var a = document.getElementsByTagName("a"), s = "";for(var i = 0; i < a.length; ++i){if(a[i].href.match(/\.(?:png|jpg|jpeg)$/i))s += a[i].href + "\n";}var t = document.createElement("textarea");t.value = s;document.getElementsByTagName("body")[0].appendChild(t);t.focus();t.select();})();
-----
微調整
typedef long long Int;
typedef vector<int> vint;
typedef pair<int,int> pint;
#define mp make_pair
template<class T> void pv(T a, T b) { for (T i=a; i!=b; ++i) cout << *i << " "; cout << endl; }
template<class T> void pvp(T a, T b) { for (T i=a; i!=b; ++i) cout << "(" << i->first << ", " << i->second << ") "; cout << endl; }
int n,m,ptr[100010],next[100010],zu[100010];
int N;
int A[100010];
int ans;
int saki(int u) {
int ret=A[u],tmp;
for (int i=ptr[u]; ~i; i=next[i]) {
tmp = saki(zu[i]);
if (tmp > 0) ret += tmp;
}
ans = max(ans, ret);
return ret;
}
int main() {
//freopen("committee.in", "r", stdin);
int u,v;
int root=0;
scanf("%i", &N);
n = N; m = 0; memset(ptr, ~0, n<<2);
for (u=0; u<N; ++u) {
scanf("%i%i", &v, &A[u]);
if (v--) {
next[m] = ptr[v]; ptr[v] = m; zu[m] = u; ++m;
} else {
root = u;
}
}
#include <cstdio>
#include <algorithm>
using namespace std;
int N, M, X[2][100010];
int greedy(int k, int d) {
int prv = X[k][0], cnt = 1;
for (int i = 1; i < M; i++) {
if (X[k][i] <= prv + d) continue;
prv = X[k][i];
cnt++;
}
return cnt;
}
int main() {
scanf("%d%d", &N, &M);
for (int i = 0; i < M; i++) scanf("%d%d", &X[0][i], &X[1][i]);
#include <cstdio>
#include <algorithm>
using namespace std;
int N, M, X[2][100010];
int greedy(int k, int d) {
int prv = X[k][0], cnt = 1;
for (int i = 1; i < M; i++) {
if (X[k][i] <= prv + d) continue;
prv = X[k][i];
cnt++;
}
return cnt;
}
int main() {
scanf("%d%d", &N, &M);
for (int i = 0; i < M; i++) scanf("%d%d", &X[0][i], &X[1][i]);
for (int k = 0; k <= 1; k++) {
for (int i = 0; i < M; i++) {
for (int j = i; j < M; j++) {
int d = X[k][j] - X[k][i];
if (greedy(0, d) + greedy(1, d) <= N) ans = min(ans, d);
}
}
}
