题解 P1561 【[USACO12JAN]爬山Mountain Climbing】

· · 题解

这是一道双机流水作业模板题。 但是直接用jhonson不等式会锅,之前我的程序就被fjtcin大佬hack了 于是我痛定思痛,决定用技(xuan)术(xue)来防止目前程序所造成的一系列问题

#include<bits/stdc++.h>
using namespace std;
struct ss{
    int a,b,c;
}dp[25005];
bool cmp(const ss u,const ss v)
{
    return(min(u.a,v.b)<min(v.a,u.b))?1:0;//引用johnson不等式
}
int main()
{
    int n,ans=0,tb=0,op=0;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>dp[i].a>>dp[i].b;
    do
    {
        random_shuffle(dp+1,dp+n+1);//技(xuan)术(xue)
        ans=0; tb=0;
        sort(dp+1,dp+n+1,cmp);//排序
        ans+=dp[1].a;
        for(int i=1;i<n;i++)//模拟
        {
            ans+=dp[i+1].a;
            tb+=dp[i].b-dp[i+1].a;
            if(tb<0) tb=0;
        }
        op=max(ans+tb+dp[n].b,op);
    }
    while(clock()<0.8*CLOCKS_PER_SEC);
    printf("%d",op);
}

那么,不用玄学怎么做呢? 先看看我是怎么被hack 的吧,然后我就去看了看https://www.luogu.org/blog/ouuan/QAQ-p2123,然后改了下代码

至于为什么那篇博客已经说得很详细了,我就不赘述了

更改引用jhonson的方式
bool cmp(const ss u,const ss v)
{
    return min(u.a,v.b)==min(u.b,v.a)?u.a<v.a: min(u.a,v.b)==min(u.b,v.a);//引用johnson不等式
}

玄学大法好