#include<algorithm> #include<cstdio> #include<iostream> #include<vector> #define MAXN 200005 usingnamespace std; int A[MAXN], B[MAXN]; int l;; inlineintread(){ int x=0,f=1; char ch=getchar(); while (ch<'0'||ch>'9'){ if (ch=='-') f=-1; ch=getchar(); } while (ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+ch-'0'; ch=getchar(); } return x*f; } inlineintmax(int a, int b){ return a > b ? a : b; } inlineintmin(int a, int b){ return a < b ? a : b; } inlineintcalc(int a, int b){ int dis = a > b ? a - b : b - a; returnmin(dis, l - dis); } int num1[MAXN],num2[MAXN]; intmain(){ int n; n=read(),l=read(); for (registerint i = 0; i < n; ++i){ A[i]=read(); } for (registerint i = 0; i < n; ++i){ B[i]=read(); } sort(A, A + n); sort(B, B + n); int minmax = 0x7fffffff; for (registerint i = 0; i <n; ++i){ int maxn = -0x7fffffff; for (registerint j = 0; j <n; ++j){ maxn = max(maxn, calc(A[j], B[(i + j >= n) ? (i + j - n) : (i + j)])); } minmax = min(minmax, maxn); } printf("%d\n", minmax); return0; }
然后,我们有一个比较显然的优化:如果当前最大值已经比最小的最大值要大的话,就break掉。
1 2 3 4 5 6 7 8 9 10
for (registerint i = 0; i <n; ++i){ int maxn = -0x7fffffff; for (registerint j = 0; j <n; ++j){ maxn = max(maxn, calc(A[j], B[(i + j >= n) ? (i + j - n) : (i + j)])); if (maxn >= minmax){ break; } } minmax = min(minmax, maxn); }
#pragma GCC optimize (2) #pragma G++ optimize (2) #include<algorithm> #include<cstdio> #include<iostream> #include<vector> #define MAXN 200005 usingnamespace std; int A[MAXN], B[MAXN]; int l;; inlineintread(){ int x=0,f=1; char ch=getchar(); while (ch<'0'||ch>'9'){ if (ch=='-') f=-1; ch=getchar(); } while (ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+ch-'0'; ch=getchar(); } return x*f; } inlineintmax(int a, int b){ return a > b ? a : b; } inlineintmin(int a, int b){ return a < b ? a : b; } inlineintcalc(int a, int b){ int dis = a > b ? a - b : b - a; returnmin(dis, l - dis); } int num1[MAXN],num2[MAXN]; intmain(){ int n; n=read(),l=read(); for (registerint i = 0; i < n; ++i){ //scanf("%d", &A[i]); A[i]=read(),num1[i]=i; } for (registerint i = 0; i < n; ++i){ //scanf("%d", &B[i]); B[i]=read(),num2[i]=i; } random_shuffle(num1,num1+n); random_shuffle(num2,num2+n); sort(A, A + n); sort(B, B + n); int minmax = 0x7fffffff; for (registerint ii = 0; ii <n; ++ii){ int maxn = -0x7fffffff; for (registerint jj = 0; jj <n; ++jj){ int i=num1[ii],j=num2[jj]; maxn = max(maxn, calc(A[j], B[(i + j >= n) ? (i + j - n) : (i + j)])); if (maxn >= minmax){ break; } } minmax = min(minmax, maxn); } printf("%d\n", minmax); return0; }