P7478 【A】StickSuger 题解

HanPi · 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;
}