Problem H: 流量问题
Time Limit: 1 Sec Memory Limit: 128 MB Submit: 36 Solved: 11 [Submit][Status][Web Board] Description
远岛君在理科大楼五楼闲着无事，闲逛到了女厕所，发现有一个底面为1×W,高为无限大的一个没有顶盖的空水箱放在平坦的地面上，中间从左到右竖直地插入了W-1块木板，每块木板之间的间隔为1，且这些木板的高度从左到右为非递增。
由于远岛君非常无聊，于是他沿着水箱最左侧倒入一定量的水，水会沿着物理规律流动（水面可能会高于某些隔板）。水箱最左边和最右边可以看成是两块高为无穷大的隔板。你能告诉他最终的水箱状态吗？
Input
第一行只有一个整数T(T≤100)，表示测试数据组数。 第二行有两个整数W,V，本别代表水箱宽度和倒入水的体积，W不超过10，V不超过1000. 第三行有W-1个整数，分别代表第i块隔板的高度hi，该高度序列非递减。hi不超过500.
Output
每个测试数据输出一行，共W个小数，分别表示第i块水柱的高度，该高度取到小数点后一位即可，相邻数字用空格隔开
Sample Input
2 4 8 3 2 1 4 12 3 2 1 Sample Output
3.0 2.0 1.5 1.5 3.0 3.0 3.0 3.0
AC代码：
#include<cstdio> const int maxn = 15; double ans[maxn]; double h[maxn]; double p[maxn]; const double INF = 1.0 * 0x3f3f3f3f; const double eps = 1e-8; int main() { int t,w; double v,sum; scanf("%d", &t); while (t--) { sum = 0; for (int i = 0; i < maxn; i++) { ans[i] = 0; p[i] = 0; } scanf("%d %lf", &w, &v); if (w == 1) { printf("%.1lf\n",v); continue; } for (int i = 1; i <= w-1; i++) { scanf("%lf", &h[i]); sum += h[i]; } h[w] = h[w-1]; sum += h[w]; if (v < sum + eps) { for (int i = 1; i <= w; i++) { if (v > h[i] - eps) { ans[i] = h[i]; v -= h[i]; } else { ans[i] = v; break; } } for (int i = 1; i < w; i++) printf("%.1lf ",ans[i]); printf("%.1lf\n",ans[w]); continue; } for (int i = 1; i <= w; i++) ans[i] = h[i]; v -= sum; h[0] = INF; for (int i = w-1; i >= 1; i--) { p[i] = p[i+1] + ((h[i-1] - h[i]) * (w-i+1)); } int k; for (k = w-1; k >= 1; k--) { if (v < p[k] + eps) break; } double tmp = 0; for (int i = k; i <= w; i++) { tmp += h[i]; } double newH = (v+tmp) / (w-k+1); for (int i = k; i <= w; i++) ans[i] = newH; for (int i = 1; i < w; i++) { printf("%.1lf ",ans[i]); } printf("%.1lf\n",ans[w]); } return 0; }