CF981F Round Marriage

這道題其實可以用暴力水過qwq

首先可以知道一個暴力做法如下，具體地來說可以用調整法證明其正确性，但是過不了所有的點。

#pragma GCC optimize (2)
#pragma G++ optimize (2)
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
#define MAXN 200005
using namespace std;
int A[MAXN], B[MAXN];
int l;;
inline int read(){
    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;
}
inline int max(int a, int b)
{
    return a > b ? a : b;
}
inline int min(int a, int b)
{
    return a < b ? a : b;
}
inline int calc(int a, int b)
{
    int dis = a > b ? a - b : b - a;
    return min(dis, l - dis);
}
int num1[MAXN],num2[MAXN];
int main()
{
    int n;
    n=read(),l=read();
    for (register int i = 0; i < n; ++i)
    {
        A[i]=read();
    }
    for (register int i = 0; i < n; ++i)
    {
        B[i]=read();
    }
    sort(A, A + n);
    sort(B, B + n);
    int minmax = 0x7fffffff;
    for (register int i = 0; i <n; ++i)
    {
        int maxn = -0x7fffffff;
        for (register int 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);
    return 0;
}
           

然後，我們有一個比較顯然的優化：如果目前最大值已經比最小的最大值要大的話，就break掉。

#pragma GCC optimize (2)
#pragma G++ optimize (2)
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
#define MAXN 200005
using namespace std;
int A[MAXN], B[MAXN];
int l;;
inline int read(){
    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;
}
inline int max(int a, int b)
{
    return a > b ? a : b;
}
inline int min(int a, int b)
{
    return a < b ? a : b;
}
inline int calc(int a, int b)
{
    int dis = a > b ? a - b : b - a;
    return min(dis, l - dis);
}
int num1[MAXN],num2[MAXN];
int main()
{
    int n;
    n=read(),l=read();
    for (register int i = 0; i < n; ++i)
    {
        A[i]=read();
    }
    for (register int i = 0; i < n; ++i)
    {
        B[i]=read();
    }
    sort(A, A + n);
    sort(B, B + n);
    int minmax = 0x7fffffff;
    for (register int i = 0; i <n; ++i)
    {
        int maxn = -0x7fffffff;
        for (register int 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);
    }
    printf("%d\n", minmax);
    return 0;
}
           

但是，顯然這個程式在随機資料下表現良好，但是會被一些特殊資料卡掉。。。比如說這個程式就T在了第24個點

什麼？你要寫二分？too young too naive！如果資料不是随機的，我們就“構造”出随機的資料，比如說，用random_shuffle優化枚舉順序

#pragma GCC optimize (2)
#pragma G++ optimize (2)
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
#define MAXN 200005
using namespace std;
int A[MAXN], B[MAXN];
int l;;
inline int read(){
    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;
}
inline int max(int a, int b)
{
    return a > b ? a : b;
}
inline int min(int a, int b)
{
    return a < b ? a : b;
}
inline int calc(int a, int b)
{
    int dis = a > b ? a - b : b - a;
    return min(dis, l - dis);
}
int num1[MAXN],num2[MAXN];
int main()
{
    int n;
    n=read(),l=read();
    for (register int i = 0; i < n; ++i)
    {
        //scanf("%d", &A[i]);
        A[i]=read(),num1[i]=i;
    }
    for (register int 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 (register int ii = 0; ii <n; ++ii)
    {
        int maxn = -0x7fffffff;
        for (register int 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);
    return 0;
}
           

然後就A了 hhh