自动搬运

查看原文

来自洛谷，原作者为

	HanPi ‎‫‎‫‎‫‎‫

搬运于2025-08-24 22:30:16，当前版本为作者最后更新于2021-04-09 17:07:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P7478 【A】StickSuger

题目大意:

给一个字符数组 $S$ ,长度为 $n$ .求一对最大的 $(i,j)$ 使得 $i<j$ 并且 $S[i]<S[j]$ . (比较时: $i$ 更大的大, $i$ 相同则 $j$ 更大的大)

暴力解

骗分是作为一个oier来说的基本功,既然想不到正解,暴力骗分也是不错的...?

从大到小枚举 $i$ ,再从大到小寻找满足条件的 $j$ ,一旦找到就停止.由于枚举的顺序,可以证明此时为最大的那一对.

for(i=n-1;i>=1;--i)
{
    if(maxi||maxj)break;
    for(j=n;j>=i+1;--j)
    {
        if(S[j]>S[i])
        {
            maxi=i;
            maxj=j;
            break;
        }
    }
}

上述代码可以拿到51分的好成绩.

优化暴力解

看到题目中:

Subtask 1（4 points）：$S$ 只包含一种字符。

考虑该情况: $S=\{b,b,b,b,b,...,b\}$ .

按照原暴力思路,枚举 $i$ 会在后面的无解情况中浪费很多时间.于是发现:

如果当某一个 $i$ 枚举完 $j$ 后找不到解,容易证明此时对于 $i$ 前面的连续的满足 $S_i=S_x$的 $x$ 也一定不会有解,因此可以跳过.

#include <stdio.h>
char S[1000007];
int n;
int main()
{
    scanf("%d%s",&n,&S[1]);
    int i,j,maxi=0,maxj=0;
    for(i=n-1;i>=1;--i)
    {
        if(maxi||maxj)break;
        for(j=i+1;j<=n;++j)
        {
            if(S[j]>S[i])
            {
                maxi=i;
                maxj=j;
            }
        }
        while(S[i-1]==S[i]&&i>=1)i--;
    }
    if(maxi+maxj==0)puts("-1");
    else printf("%d %d",maxi,maxj);
    return 0;
}

该优化可以以 55ms 通过该题.

类似的思路

我们从大到小枚举 $j$ ,每次再从大到小寻找第一个合适的 $i$ ,如果比当前最优解更优则更新.如果枚举的 $i$ 已经小于最优解则不再枚举.

考虑该情况: $S=\{a,b,b,b,...,b\}$ , 因为后面几个相同, 容易证明 $j$ 取最后一个一定会比取前几个更优,因此当枚举完一个 $j$ 后可以直接跳过相同的.

#include <stdio.h>
int n;
char S[1000007];
int main()
{
    scanf("%d%s",&n,&S[1]);
    int i,j,a,b,maxi=0,maxj=0;
    for(j=n;j>=1;--j)
    {
        a=0,b=0;
        for(i=j-1;i>=1;--i)
        {
            if(S[i]<S[j])
            {
                a=i;
                b=j;
                break;
            }
            if(i<=maxi)break;
        }
        if(a>maxi)
        {
            maxi=a;
            maxj=b;
        }
        else if(a==maxi&&b>maxj)
        {
            maxi=a;
            maxj=b;
        }
        while(S[j-1]==S[j]&&j>=1)
        {
            j--;
        }
    }
    if(maxi+maxj==0)puts("-1");
    else printf("%d %d",maxi,maxj);
    return 0;
}