• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

codeforces460C.Present解题报告

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

题目链接:http://codeforces.com/submissions/ywindysai

题目意思:有 n 朵花,每朵花都有一定的高度(第 i 朵花对应 ai),m 天之后要把这些花送给别人。不过这 m 天里可以通过淋花来让花长得尽可能高啦(当然不希望把长得矮矮的花送给人啦),每天只能淋一次,一次覆盖的范围是连续的 w 朵,淋完水后被淋的花会在当天长高 1 个单位(one height unit)。现在就问,m天之后,最矮的那朵花最高能长到多高。

     首先,我对这条题目完全没有想法,四个字:无从下手!好啦,直接看题解,英文太差,有些地方看不懂,直接看代码,还是有点不懂,手动模拟终于明白了^_^

     总体的思路就是:二分找出这个高度!(姑且说它为期望值X)。计算出这 n 朵花是否每朵都能够在这 m 天内长到X 那么高。怎么找是一个关键。假设花从左到右是从0~n-1编号的。

     对于每个期望值X(二分,使得即使X好大,也只是O(log2N),N 最大为1e14(10^5 × 10^9)),我们都要按顺序遍历这 n 朵花(在我看来,按顺序来做确实可以化繁为简,将问题简单化)。首先对于前 w 多花,它们都不能借助前面花的淋水次数来减少它们被淋的次数(通过段来减少,就是w 啦),因为它们是最先嘛。那么第一朵花得到期望值X要淋X-a[0] 天了,而接下来连续的w-1朵就可以少淋 X-a[0] 这么多天了,而且这w-1朵可以在原来的高度下长高X-a[0] 的高度。不过w-1朵之后的花就不能依靠第一朵花被淋的次数了(只能覆盖w段),不过对于 i (i >= w)的每朵花,它可以依靠i-1, i-2,...,i-w 朵花被淋的次数来长高相应高度,这样往往可以使得当第 i 朵花要到达期望值时的淋水天数少于它本来最多要淋的次数(X - a[i])

     

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <vector>
 6 using namespace std;
 7 
 8 typedef long long ll;
 9 const ll maxn = 1e14;
10 
11 vector<ll> a;
12 ll m, w, n;
13 
14 bool check(ll x)
15 {
16     ll move = 0;
17     ll scur = 0;
18     vector<ll> s(n+1, 0);    // s 的 n+1个元素初始值都为0
19     for (ll i = 0; i < n; i++)
20     {
21         scur -= (i >= w ? s[i-w] : 0);  // 刚开始的w-1朵花不能依靠前面花的被淋天数来增高,之后的都可以 
22         if (x > a[i] + scur)
23         {
24             s[i] = x - scur- a[i];   // 第i朵花要达到x实际还需要x-scur-a[i]这么多天
25             scur += s[i];           // 更新次数,之后的w-1朵花可以减少淋scur那么多天
26             move += s[i];            // 累积天数
27         }
28         if (move > m)
29             return false;
30     }
31     return true;  // move <= m
32 }
33 
34 int main()
35 {
36     while (scanf("%lld%lld%lld", &n, &m, &w) != EOF)
37     {
38         a.resize(n+1);   // 设 a 的 size和capacity 为 n+1(其实n也可以)
39         for (int i = 0; i < n; i++)
40             scanf("%lld", &a[i]);
41         ll left = 1, right = maxn;
42         ll X = 0;
43         while (left <= right)  // < 是错的,一定是 <=
44         {
45             ll mid = (left+right) >> 1;
46             if (check(mid))     // 代表每朵花都可以在 m 天内达到mid的高度
47             {
48                 X = mid;
49                 left = mid + 1;
50             }
51             else
52                 right = mid - 1;
53         }
54         printf("%lld\n", X);
55     }
56     return 0;
57 }
View Code

    题解说线段树也能做

   http://codeforces.ru/blog/entry/13465?locale=en

     总的来说,C题都是比较考思维滴!!!


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
C++计算一个程序运行时间,精确到毫秒发布时间:2022-07-13
下一篇:
C#操作摄像头发布时间:2022-07-13
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap