【洛谷p1031】均分纸牌

时间：2024-01-03 22:26:50

【博客园的第一条随笔，值得纪念一下】

均分纸牌【传送门】

洛谷上的算法标签是

【洛谷p1031】均分纸牌

这道题是一道贪心题，过了四遍才过（蒟蒻有点废）

第一遍的时候考虑的非常少，只想到了求出平均数→求差值→从左往右加差值；

这样出来的结果永远是n-1，只过了一个点。

附上错误想法（不要被误导）：

#include<iostream>

#include<cstdio>

using namespace std;

int n,a[],sum=,c[],b,ans=;

int t();

int main()

{

    cin>>n;

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

    {

        cin>>a[i];

        sum+=a[i];

    }

    b=sum/n;

    t();

}

int t()

{

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

        c[i]=a[i]-b;

        for(int j=;j<=n;j++)

        {

            c[j]+=c[j-];

            ans++;

        }

    cout<<ans<<endl;

}

第二遍就慌了，也只过了一个点。

第二遍的时候在第一步基础上加了if语句，然鹅还是错的。

连错两遍，我慌了。第三遍仔细的拿纸笔想了一下错误是怎么造成的（但只是拿洛谷下载下来的错误的测试数据），虽然测试数据对了，然鹅只是对于测试数据程序是合适的，对其他例子就不合适了【所以提醒做题一定不能看个例，要看整体】

第四次真的深思熟虑了一番，改进了许多，终于过了。

附上ac代码：

#include<iostream>

#include<cstdio>

using namespace std;

int n,a[],sum=,c[],b,ans=;

int t();

int main()

{

    cin>>n;

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

    {

        cin>>a[i];

        sum+=a[i];

    }

    b=sum/n;

    t();

}

int t()

{

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

        c[i]=a[i]-b;

    int i=,j=n;

        while(c[i]==&&i<n) i++;

        while(c[j]==&&j>) j--;

    while(i<j)

    {

        c[i+]+=c[i];

        c[i]=;

        ans++;

        i++;

        while(c[i]==&&i<j)i++;

    }

    cout<<ans<<endl;

}

end-

相关文章