四, 跳房子
[题目描述]
跳房子, 也叫跳飞机, 是一种世界性的儿童游戏, 也是中国民间传统的体育游戏之一.
跳房子的游戏规则如下:
在地面上确定一个起点, 然后在起点右侧画 n 个格子, 这些格子都在同一条直线上. 每个格子内有一个数字 (整数), 表示到达这个格子能得到的分数. 玩家第一次从起点开始向右跳, 跳到起点右侧的一个格子内. 第二次再从当前位置继续向右跳, 依此类推. 规则规定:
玩家每次都必须跳到当前位置右侧的一个格子内. 玩家可以在任意时刻结束游戏, 获得的分数为曾经到达过的格子中的数字之和.
现在小 R 研发了一款弹跳机器人来参加这个游戏. 但是这个机器人有一个非常严重的缺陷, 它每次向右弹跳的距离只能为固定的 d. 小 R 希望改进他的机器人, 如果他花 g 个金币改进他的机器人, 那么他的机器人灵活性就能增加 g, 但是需要注意的是, 每次弹跳的距离至少为 1. 具体而言, 当 g<d 时, 他的机器人每次可以选择向右弹跳的距离为 d?g,d?g+1,d?g+2,...,d+g-2,d+g?1,d+g; 否则 (当 g≥dg 时), 他的机器人每次可以选择向右弹跳的距离为 1,2,3,...,d+g?2,d+g?1,d+g .
现在小 R 希望获得至少 k 分, 请问他至少要花多少金币来改造他的机器人.
[输入格式]
第一行三个正整数 n,d,k, 分别表示格子的数目, 改进前机器人弹跳的固定距离, 以及希望至少获得的分数. 相邻两个数之间用一个空格隔开.
接下来 n 行, 每行两个正整数 xi,si, 分别表示起点到第 i 个格子的距离以及第 i 个格子的分数. 两个数之间用一个空格隔开. 保证 xi 按递增顺序输入.
[输出格式]
共一行, 一个整数, 表示至少要花多少金币来改造他的机器人. 若无论如何他都无法获得至少 k 分, 输出? 1 .
[输入样例一]
- 7 4 10
- 2 6
- 5 -3
- 10 3
- 11 -3
- 13 1
- 17 6
- 20 2
[输出样例一]
2
[输入样例二]
- 7 4 20
- 2 6
- 5 -3
- 10 3
- 11 -3
- 13 1
- 17 6
- 20 2
[输出样例二]
-1
[输入输出样例 1 说明]
2 个金币改进后, 小 R 的机器人依次选择的向右弹跳的距离分别为 2,3,5,3,4,3, 先后到达的位置分别为 2,5,10,13,17,20, 对应 1,2,3,5,6,7 这 6 个格子. 这些格子中的数字之和 15 即为小 R 获得的分数.
[输入输出样例 2 说明]
由于样例中 7 个格子组合的最大可能数字之和只有 18, 无论如何都无法获得 20 分.
[数据规模与约定]
本题共 10 组测试数据, 每组数据 10 分.
对于全部的数据满足 1≤n≤500000,1≤d≤2000,1≤xi,k≤109,∣si∣<105.
对于第 1,2 组测试数据, n≤10;
对于第 3,4,5 组测试数据, n≤500;
对于第 6,7,8 组测试数据, d=1.
[解析]
- #include<bits/stdc++.h>
- using namespace std;
- struct node{
- int x,v;
- }q[500005];
- int f[500005];
- long long maxx=0;
- int n,d,k;
- int dis[500005],sc[500005];
- bool check (int g)
- {
- int low=max (1,d-g),high=d+g;
- int cur=0,head=0,tail=-1;
- memset (f,0,sizeof (f));
- for (int i=1;i<=n;i++)
- {
- for (;cur<i&&dis[cur]<=dis[i]-low;cur++)
- {
- while (head<=tail&&q[tail].v<f[cur])
- tail--;
- if (f[cur]!=-0x3f3f3f3f)
- q[++tail].v=f[cur],q[tail].x=dis[cur];
- }
- while (head<=tail&&dis[i]-q[head].x>high)
- head++;
- f[i]=(head<=tail)?q[head].v+sc[i]:-0x3f3f3f3f;
- if (f[i]>=k)
- return 1;
- }
- return 0;
- }
- int main()
- {
- scanf ("%d%d%d",&n,&d,&k);
- for (int i=1;i<=n;i++)
- {
- scanf ("%d%d",&dis[i],&sc[i]);
- maxx+=max (sc[i],0);
- }
- if (maxx<k)
- {
- printf ("-1");
- return 0;
- }
- int l=1,r=dis[n];
- while (l<r)
- {
- int mid=(l+r)/2;
- if (check (mid))
- r=mid;
- else
- l=mid+1;
- }
- printf ("%d",l);
- return 0;
- }
以上代码是 AC 代码, 用单调队列, 属于提高组的解法.
来源: http://www.bubuko.com/infodetail-2966218.html