| 题目名称 | 278. [USACO Jan09] 气象牛 |
|---|---|
| 输入输出 | baric.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 2481
于2015-07-08加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：92， 提交：197， 通过率：46.7% | ||||
 Hzoi_Yniverse |
100 | 0.000 s | 0.00 MiB | C++ |
|
Hzoi_Yniverse |
100 | 0.000 s | 0.00 MiB | C++ |
 Anonymity |
100 | 0.000 s | 0.00 MiB | C++ |
 瑆の時間~無盡輪迴·林蔭 |
100 | 0.000 s | 0.00 MiB | C++ |
 面对疾风吧 疾风 疾风吧 |
100 | 0.000 s | 0.54 MiB | C++ |
 ONCE AGAIN |
100 | 0.004 s | 0.35 MiB | C++ |
 Twilight_Dark |
100 | 0.004 s | 0.69 MiB | C++ |
 Sky_miner |
100 | 0.005 s | 0.37 MiB | C++ |
|
ONCE AGAIN |
100 | 0.005 s | 0.39 MiB | C++ |
 MiracleEEEE |
100 | 0.006 s | 0.38 MiB | C++ |
| 本题关联比赛 | |||
| 20110414pm | |||
| 20110414pm | |||
| NOIP2017普及组模拟赛Mike | |||
| 关于 气象牛 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
回复 @码农李 :
wy  zyh
2015-11-03 13:53
6楼
| ||||
|
楼上yuanzheng大神的80分代码改进，0.06s超神代码，80分是因为最大值太小，开成1<<30就可以了。
 | ||||
|
| ||||
|
咦好像在哪里做过的样子
 ztx
2015-07-27 11:23
3楼
| ||||
|
| ||||
|
| ||||
霓虹灯下的码农
yuanzheng
lenibomb
JSX气象牛 [Jeffrey Wang, 2007]
为了研究农场的气候,Betsy帮助农夫John做了N(1 <= N <= 100)次气压测量并按顺序记录了结果M_1...M_N(1 <= M_i <= 1,000,000).
Betsy想找出一部分测量结果来总结整天的气压分布.她想用K(1 <= K <= N)个数s_j (1 <= s_1 < s_2 < ... < s_K <= N)来概括所有
测量结果. 她想限制如下的误差:对于任何测量结果子集,每一个非此子集中的结果都会产生误差.总误差是所有测量结果的误差之和.
更明确第说,对于每一个和所有s_j都不同的i:
如果 i 小于 s_1, 误差是: 2 * | M_i - M_(s_1) |
如果i在s_j和s_(j+1)之间,误差是: | 2 * M_i - Sum(s_j, s_(j+1)) |
注:Sum(x, y) = M_x + M_y; (M_x 和 M_y 之和) *
如果i大于s_K,误差为: 2 * | M_i - M_(s_K) |
Besty给了最大允许的误差E (1 <= E <= 1,000,000),找出最小的一部分结果使得误差最多为E.
输入格式:
第一行: 两个空格分离的数: N 和 E * 第2..N+1行: 第i+1行包含一次测量记录:M_i
输出格式:
第一行: 两个空格分开的数: 最少能达到误差小于等于E的测量数目和使用那个测量 数目能达到的最小误差.
样例输入:
4 20 10 3 20 40
输入解释:
Bessie做了4次记录,分别为10,3,20,和40.最大允许误差是20.
样例输出 :
2 17
输出解释:
选择第二和第四次测量结果能达到最小误差17. 第一次结果的误差是2*|10-3| = 14; 第三次结果的误差是|2*20 - (3+40)|=3.