题解：P13145 [GCJ 2018 #2] Falling Balls

· · 题解

贪心好题。

思路

此题较小的数据和较大的时间容易让人误以为是其他算法，但是其实就是贪心。

下证贪心是正确的：

对于每个球，管辖它的接收点与它必定是一条直线，再加自由落体，又任意接收点管辖的是一个区间内的球，因此，所设计的算法中不可能有两个球的滑道交叉，因此可行。

下证贪心是最优解：

对于 1 号接收点，管辖区域必定为 1 至 a_1，否则必存在 1 \le i \le a_1 使得 i 号球被 2 至 n 号接收点管辖，则必有交叉，得证。同理对 2 至 n 号接受点，管辖的范围一定是唯一的，又因为对于每个球，管辖它的接收点与它必定是一条直线，所以一定最短，所以知贪心得到最优解。

判断无解情况：

由前分析得，可构造出解法，但是因为 1 和 n 列不能放置斜板，所以 1 和 n 号球必定掉落在 1 和 n 号接受点，所以如果 a_1 或 a_n 是 0，则无解。

代码

//code by Dreamer_002
#include<cstdio>
#include<cstring>
const int N = 105;
int T,Case,n,a[N],ans;
char mp[N][N];
int maxx(int a,int b){
    return a>b?a:b;
}
int main(){
    scanf("%d",&T);
    while(T--){
        memset(mp,0,sizeof(mp));ans=0;
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
        }
        Case++;printf("Case #%d: ",Case);
        if(a[1]==0 || a[n]==0){//只有两边不能加斜边，所以两边一定有球落下，否则无解。
            printf("IMPOSSIBLE\n");
            continue;
        }
        int now=0;
        for(int i=1;i<=n;i++){//now+1 ~ now+a[i] -> i
            for(int j=now+1;j<=now+a[i];j++){
                if(j<i){//球的编号比接收点小，向右斜
                    for(int ki=1,kj=j;kj<i;ki++,kj++){
                        mp[ki][kj]='\\';
                        ans=maxx(ans,ki);
                    }
                }
                else if(j>i){//球的编号比接受点大，向左斜
                    for(int ki=1,kj=j;kj>i;ki++,kj--){
                        mp[ki][kj]='/';
                        ans=maxx(ans,ki);
                    }
                }
            }
            now+=a[i];
        }
        printf("%d\n",ans+1);//最下面要求留一个空行
        for(int i=1;i<=ans+1;i++){//输出
            for(int j=1;j<=n;j++){
                if(mp[i][j]=='\\' || mp[i][j]=='/'){
                    printf("%c",mp[i][j]);
                }
                else{
                    printf(".");
                }
            }
            printf("\n");
        }
    }
    return 0;
}

总结

从分析到实践，这是道贪心与构造揉合的好题，希望大家也能细细钻研证明过程，终。