C - Balls and Boxes CodeForces - 260C

题意：编号1-n个桶，每个桶里有ai个球，现在从下标为i的桶里，拿出所有的球，一直往右边放，放到n了，就再从0开始放，告诉你最后一个球放下的下标，要你输出所有桶的最初状态。对于最初的代码，有一个没想到的bug是所有的数字都相同的情况下，下面的代码能够解决这样的问题，还是思考的不严密。

思路：桶内球最少的那个下标，肯定是拿出球的桶。那么我们把所有从桶下标+1到桶的下标的球全部先拿出来，用T来保存，即T=minn*n。这些球都是从桶拿出来的，然后对于ed最后的下标，我们就往前搜，直到碰到0为止。如果ed==0,ed=n; 因为在一般情况下，值为0的肯定只能是拿出的那个桶。对于特殊情况下，有部分桶的值相同的情况下，用上面的思路可以很好的解决多个0的问题，那么从ed出发往左，第一个碰到的0就是拿出球的桶。如果不是第一个为0的，而是第k个为0的情况，那么前k个0的球数量就会小于0，明显不合题意。

一开始写代码：我先找到min最小的小标，和上面正确的思路一样做。结果你会发现前3个样例都会通过，而第四个死活过不去。因为你要找min最小的下标，如果数据中存在多个相同的值，那么你要选哪个？？？这没法选吧？马后炮，分析可以知道如果有多个相同的值，一定是ed往左最先碰到的那个0才对，否则就会出现负值的问题。在最下面我贴上有问题的代码。

/*If I get TLE , it is good.If I get AC,it's NICE !*/
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <cmath>
#include <queue>
#include <string>
#include <map>
using namespace std;
typedef long long ll;
const int INF=2147483647;
const int MAXN=1e5+10;
const ll mod=1e9+7;
using namespace std;
typedef long long ll;
ll a[MAXN];
int main(void)
{
    ll n,ed;
    cin >> n >> ed;
    ll minn=INF;
    for(int i=1; i<=n; i++)
    {
        scanf("%I64d",&a[i]);
        if(a[i]<minn)
        {
            minn=a[i];
        }
    }
    ll T=minn;
    for(int i=1; i<=n; i++)   a[i]=a[i]-T;
    T=T*n;
    /*for(int i=1;i<=n;i++) { if(i==1) printf("%d",a[i]); else printf(" %d",a[i]); } cout <<T << endl;*/
    while(a[ed]!=0)
    //这个循环里的语句非常有讲究，你必须先对a[ed]--,再ed--，否则会出事的。其实这些都是模拟过程的BUG所在，你可能永远都找不出自己的思路，所以有时候可能代码重新打一次效果会好一点。
    {
        T++,a[ed]--,ed--;
        if(ed==0)   ed=n;
        //cout << T << " "<< ed <<endl;
    }
    a[ed]=T;
    for(int i=1;i<=n;i++)
    {
        if(i==1)    printf("%I64d",a[i]);
        else    printf(" %I64d",a[i]);
    }
    puts("");
}

/*If I get TLE , it is good.If I get AC,it's NICE !*/
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <cmath>
#include <queue>
#include <string>
#include <map>
using namespace std;
typedef long long ll;
const int INF=2147483647;
const int MAXN=1e5+10;
const ll mod=1e9+7;
using namespace std;
typedef long long ll;
ll a[MAXN];
int main(void)
{
    int n,ed;
    cin >> n >> ed;
    ll minn=INF,index;
    for(int i=1; i<=n; i++)
    {
        scanf("%I64d",&a[i]);
        if(a[i]<minn)
        {
            minn=a[i];
            index=i;
        }
    }
    ll T=minn;
    for(int i=1; i<=n; i++)   a[i]=a[i]-T;
    T=T*n;
    if(ed >= index)
    {
        for(int i=index+1; i<=ed; i++)
        {
            T++;
            a[i]--;
        }//printf("T=%d",T);
    }

    else
    {
        for(int i=1; i<=ed; i++)
        {
            T++;
            a[i]--;
        }
        for(int i=index+1; i<=n; i++)
        {
            T++;
            a[i]--;
        }
    }
    a[index]=T;
    for(int i=1;i<=n;i++)
    {
        if(i==1)    printf("%d",a[i]);
        else    printf(" %d",a[i]);
    }
    puts("");
}

通过这题，I GET WHAT?
1.模拟思路，一定要在脑海里过一遍，不要傻想，对模拟的过程一定要自习分析，每条语句写出来，要有理有据。
2.对于特殊情况，一定要多加思考。

C - Balls and Boxes CodeForces - 260C

全站热榜

创作者周榜