P2123 ----- 赌神与hack的搏斗 2

· · 题解

P1561 ----- 赌神与hack的搏斗。

这道题是与 P1561 相同的大水题。

在上面链接的题解中，有讲 Johnson 不等式与 knuth 算法随机化。

先用 Johnson 不等式排序。

用 knuth 算法随机打乱序列去做。

改一下输入与多测，交一发。

95 pts。

这题 Hack 数据显然比上题要大。

LBY 这个蒟蒻尝试了几十次，终于，一个能通过的简单的随机算法来了。

按照 dalao 说的，Johnson 不等式不具有不具有不可比性的传递性。

所以在不同序列上，有不同的答案。

于是我们在每次 knuth 后，直接用 Johnson 排一下序。

我不信还不能排出所有序列。

于是就过了。

AC 记录。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
struct node{
    int a,b;
}a[20010];
inline void knuth(){//knuth算法 
    for(int i=1;i<=n;i++)
        swap(a[1],a[rand()%n+1]);
}
inline int count(){
    int sum=0,ans=0;
    for(int i=1;i<=n;i++){
        sum+=a[i].a;
        ans=max(ans,sum)+a[i].b;
    }
    return ans;
}
bool cmp(node x,node y){
    return (min(x.a,y.b)<min(x.b,y.a)) ? 1 : 0;
}
inline void solve(){
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i].a>>a[i].b;
    sort(a+1,a+n+1,cmp);
    int cnt=0,ans=2e15;
    while(cnt+2*n<=2e6){//时间足够就继续枚举 
        cnt+=2*n;
        int p=count();
        ans=min(ans,p);
        knuth();
        sort(a+1,a+n+1,cmp);
    }
    cout<<ans<<"\n";
}
signed main() {
    ios::sync_with_stdio(0);
    srand(time(0));
    int t;
    cin>>t;
    while(t--) solve();
    return 0;
}

细节

首先，这份代码需要你有把控时间的能力。

你需要判断这个时间是否能过。

第二，把打乱时间的 2 \times 10^6 改为 10^6 就过不了，所以你要对随机有把控。

第三，2\times 10^6 需要加入 inline 与 ios 优化才能过，这种需要足够的卡常。