2012-0078

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

令x=max(r[i-1],l[i])， 然后total=s+max(x)。 用dmin[i]记录第i个餐馆和第一个餐馆相同的菜的最小值，dmax[i]是最大值，然后递推出dmin[n-1] 比较 dmin[n-1]+x-s的大小，添加到结果中。
递推在源代码里。
{{{
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;


void SAISEI(int n, int m, int t1, int t2, int L[], int R[])
{
srand(t1);
for (int i = 0; i < n; i++)
L[i] = rand() % m;
srand(t2);
for (int i = 0; i < n; i++)
R[i] = rand() % m;
}

int main()
{
    //freopen("in","r",stdin); 
    //freopen("out","w",stdout);
    int n,s,t1,t2,m;
    while(cin>>n>>s>>t1>>t2>>m)
    {
        int l[200001];
        int r[200001];
        int dmin[200001];
        int dmax[200001];
        SAISEI(n,m,t1,t2,l,r);
        int flag=0;
        dmin[0]=s;
        dmax[0]=s;
        int total=0;
        for(int i=0;i<n;i++)
        {
            if(s<r[i]||s<l[i])
            {
                cout<<"AHOU\n";
                flag=1;
                break;
            }
            total=max(total,s+max(r[i],l[(i+1)%n]));
        }
        if(flag==1)
            continue;
        for(int i=1;i<n;i++)
        {
            int x=max(r[i-1],l[i]);
            if(x<dmin[i-1])
            {
                dmin[i]=max(0,x-total+2*s-dmin[i-1])+dmin[i-1]-x; 
            }
            else if(x>dmax[i-1])
            {
                dmin[i]=max(0,x-total+2*s-dmax[i-1]);
            }
            else
            {
                dmin[i]=max(0,2*s-total);
            }
            if(s-x<dmin[i-1])
            {
                dmax[i]=s-x+min(s-dmin[i-1],x);
            }
            else if(s-x>dmax[i-1])
            {
                dmax[i]=min(x+dmax[i-1],s);
            }
            else
            {
                dmax[i]=s;
            }
        }
        int x=max(r[n-1],l[0]);
        if(dmin[n-1]+x>s)
        {
            total=total+dmin[n-1]+x-s;
        }
    cout<<total<<"\n";
    }
   // fclose(stdin);
   // fclose(stdout); 
    return 0;
}

令x=max(r[i-1],l[i])， 然后total=s+max(x)。 用dmin[i]记录第i个餐馆和第一个餐馆相同的菜的最小值，dmax[i]是最大值，然后递推出dmin[n-1] 比较 dmin[n-1]+x-s的大小，添加到结果中。

递推在源代码里。

{{{

#include

#include

#include

using namespace std;

void SAISEI(int n, int m, int t1, int t2, int L[], int R[])

{

srand(t1);

for (int i = 0; i < n; i++)

L[i] = rand() % m;

srand(t2);

for (int i = 0; i < n; i++)

R[i] = rand() % m;

}

int main()

{

//freopen("in","r",stdin);

//freopen("out","w",stdout);

int n,s,t1,t2,m;

while(cin>>n>>s>>t1>>t2>>m)

{

int l[200001];

int r[200001];

int dmin[200001];

int dmax[200001];

SAISEI(n,m,t1,t2,l,r);

int flag=0;

dmin[0]=s;

dmax[0]=s;

int total=0;

for(int i=0;i

{

if(s

{

cout<<"AHOU\n";

flag=1;

break;

}

total=max(total,s+max(r[i],l[(i+1)%n]));

}

if(flag==1)

continue;

for(int i=1;i

{

int x=max(r[i-1],l[i]);

if(x

{

dmin[i]=max(0,x-total+2*s-dmin[i-1])+dmin[i-1]-x;

}

else if(x>dmax[i-1])

{

dmin[i]=max(0,x-total+2*s-dmax[i-1]);

}

else

{

dmin[i]=max(0,2*s-total);

}

if(s-x

{

dmax[i]=s-x+min(s-dmin[i-1],x);

}

else if(s-x>dmax[i-1])

{

dmax[i]=min(x+dmax[i-1],s);

}

else

{

dmax[i]=s;

}

}

int x=max(r[n-1],l[0]);

if(dmin[n-1]+x>s)

{

total=total+dmin[n-1]+x-s;

}

cout<

}

// fclose(stdin);

// fclose(stdout);

return 0;

}