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

贪心好题。

思路

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

考虑每个接受点（底部）管辖的球，是一个区间，按照从小到大，即 $1$ 号管辖 $1$ 至 $a_1$ 号球， $2$ 号管辖 $a_1+1$ 至 $a_1+a_2$ 号球，以此类推。
构造图即可。

下证贪心是正确的：

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

下证贪心是最优解：

对于

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

，则无解。

代码

CPP

//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;
}

总结

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

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

文章操作

思路

代码

总结

相关推荐

评论

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