2012年12月23号竞赛题目一
主办方:百度公司
时间:2012-12-23 18:00 至 2012-12-24 00:00
Du熊做实验
Time Limit : 1000ms Memory Limit : 65535K
Problem Description
du熊是个爱学习的孩子,他总喜欢在生活中做一些小实验,这次du熊想研究一下光合作用。
du熊的实验材料有如下几样:神奇的种子,普通的纸箱和一些光源。一开始du熊将种子均匀的种在了箱子底部,你可以将其看成X轴,种子的位置为X轴上的点。然后du熊用纸板将箱子盖住,并在纸板上安装了一些光源(具体见图)。神奇的种子会在有光的情况下一直向上生长直到没光为止。现在du熊想知道当实验结束时每颗种子的高度是多少?
顶上的为光源,光源两边与顶部的夹角都为45°,黄色部分为光照,绿色的为植物。
Input
第一行给出一个T,表示测试数据的组数。
每组数据的第一行是三个整数n,m,H(1<=n<=100,000, 0<=m<=100,000, 1<=H<=10,000),n表示种子数(编号1-n),m表示光源数,H表示箱子的高度。接下来m行,每行一个整数Xi表示第i个光源在顶部的位置。
Output
对于每组测试数据,请输出n行,每行一个数表示第i颗种子的最终高度。
Sample Input
2
7 1 2
4
4 4 1
1
2
3
4
Sample Output
0
0
1
2
1
0
0
1
1
1
1
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAXN = 100000 + 10; int seed[MAXN]; int light[MAXN]; int main () { int t; scanf ("%d",&t); while (t--) { int n,m,h; int i,j; memset (seed,0,sizeof (seed)); scanf ("%d%d%d",&n,&m,&h); for (i = 0; i < m; i++) { scanf ("%d",&light[i]); } sort (light,light + m); for (i = 1; i <= light[0]; i++) { seed[i] = i > light[0] - h ? i - light[0] + h : 0; } for (i = 0; i < m - 1; i++) { for (j = light[i]; j <= light[i + 1]; j ++) { int s1 = j < light[i] + h ? light[i] - j + h : 0; int s2 = j > light[i + 1] - h ? j - light[i + 1] + h : 0; seed[j] = s1 > s2 ? s1 : s2; } } for (i = light[m - 1]; i <= n; i++) { seed[i] = i < light[m - 1] + h ? light[m - 1] - i + h : 0; } for (j = 1; j <= n; j++) { printf ("%d\n",seed[j]); } } }