Vasya is interested in arranging dominoes. He is fed up with common dominoes and he uses the dominoes of different heights. He put ndominoes on the table along one axis, going from left to right. Every domino stands perpendicular to that axis so that the axis passes through the center of its base. The i-th domino has the coordinate xi and the height hi. Now Vasya wants to learn for every domino, how many dominoes will fall if he pushes it to the right. Help him do that.
Consider that a domino falls if it is touched strictly above the base. In other words, the fall of the domino with the initial coordinate x and height h leads to the fall of all dominoes on the segment [x + 1, x + h - 1].
The first line contains integer n (1 ≤ n ≤ 105) which is the number of dominoes. Then follow n lines containing two integers xi and hi ( - 108 ≤ xi ≤ 108, 2 ≤ hi ≤ 108) each, which are the coordinate and height of every domino. No two dominoes stand on one point.
Print n space-separated numbers zi — the number of dominoes that will fall if Vasya pushes the i-th domino to the right (including the domino itself).
4 16 5 20 5 10 10 18 2
3 1 4 1
4 0 10 1 5 9 10 15 10
4 1 2 1
题意:
给出 n(1 ~ 100000),代表有 n 张牌,后给出 n 张牌的 x 坐标和 h 高度,问每张牌向右倒的话,一共最多能倒多少张牌。
思路:
排序。记录每张牌能到达的最远的坐标 next,输出顺序 idex,x 坐标 num,最大能到达的牌数 to。先对 num 由小到大 sort 一遍,后从最后一张牌开始往后倒,因为最后一张牌倒的话只有 1 张,之后判断的时候,判断能不能使下一张牌倒下,如果能则这张牌倒下的牌数加上下一张牌的倒排数,同时跳到这张牌能到达的最远牌数(即 num [ i ].to += num [ i + 1 ].to 且 to += no [ i + 1 ].to )。最后输出的时候按 idex 由小到达再 sort 一遍后,一次输出 to 即可。
比赛的时候心态很重要。对于边界处理真的是非常烦躁,明明会做的题一直卡在代码的实现上,有时候又因为太过紧张而漏洞百出,忘这忘那呢,思路又混乱,必须提高思维的练习才行。
AC:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAX = 100005; typedef struct { int idex, num, next, to; }node; node no[MAX]; bool cmp1 (node a, node b) { return a.num < b.num; } bool cmp2 (node a, node b) { return a.idex < b.idex; } int main() { int n; scanf("%d", &n); for (int i = 0; i < n; ++i) { int ans; scanf("%d%d", &no[i].num, &ans); no[i].next = no[i].num + ans - 1; no[i].idex = i; } sort(no, no + n, cmp1); no[n - 1].to = 1; for (int i = n - 2; i >= 0; --i) { int t = i + 1; no[i].to = 1; while (t < n && no[t].num <= no[i].next) { no[i].to += no[t].to; t += no[t].to; } } sort(no, no + n, cmp2); for (int i = 0; i < n; ++i) { printf("%d", no[i].to); i == n - 1 ? printf("\n") : printf(" "); } return 0; }
相关推荐
GO访问domino、通过http访问Domino、GO快速访问Domino、GO集成domino 完全提供源码 界面请查阅 https://blog.csdn.net/weijia3624/article/details/113108704
IBM lotus domino server 7.0
C#访问domino,通过http访问Domino,C#快速访问Domino,C#集成lotus domino 完全提供源码 界面请查阅 https://blog.csdn.net/weijia3624/article/details/113108704
java访问domino,通过http访问Domino,java快速访问Domino,java集成lotus domino 完全提供源码 界面请查阅 https://blog.csdn.net/weijia3624/article/details/113108704
Domino接口编程及Domino程序优化
domino公式大全,中文说明,让更快速、明了的开发domino
Domino 邮件系统具有三个基本组件:Domino 邮件服务器、Domino 邮件文件和邮件客户机。Domino 邮件服务器是组织消息处理基础结构的核心,它既是 Internet 邮件服务器又是 Notes 邮件服务器。Domino 通过它对 SMTP...
Domino管理配置,window下安装domino
domino漂亮登陆界面,使用bootstrap,把数据库直接放到data文件夹下 详情请浏览 https://blog.csdn.net/weijia3624/article/details/48338045
Domino服务器安装文档Domino lotus
python访问domino、通过http访问python、python快速访问Domino、python集成domino 完全提供源码 界面请查阅 https://blog.csdn.net/weijia3624/article/details/113108704
Notes.jar lotus.domino.* java连接domino 没有分数的可以到 http://www.ibm.com/developerworks/apps/download/index.jsp?contentid=50943&filename=DominoJSPArticle.zip&method=http&locale=worldwide
Domino notes java版导出excel,需要组件poi支持,解决Domino日常数据批量导出需求!
Lotus Domino安装、配置和管理
workflow Domino workflow Domino workflow Domino workflow Domino
Domino Web视图设计: Domino Web视图的表现方法 Domino视图在Web上显示方式 如何构建指定风格的视图
Domino5.08服务器升级到Domino6.53服务器(IBM推荐) --- WIN2000操作系统
Domino获取在线用户,Domino获取BS在线用户
在Lotus Domino中应用WebService,Domino的WebService服务
domino Web 开发资料介绍了用domino作为web服务器来进行应用系统开发的基本知识