Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
欢迎参加IJCAI 2020麻将智能体竞赛,大奖等你拿!Welcome to IJCAI 2020 Mahjong AI competition with amazing prizes! | 北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

第一个树状数组..留爪..说说思路..

Posted by zzyzzy12 at 2011-03-20 23:24:05 on Problem 2828
前面很多也提到了..就是先都读完(ki,xi)..再从后往前添加..
添加时..譬如添加的ki=5..那么他的位置就是从第一个开始..数到第6个空的位置(没被占的位置)..然后填上这个数..这个位置标记已占..而且这个数的位置就确定了..不再动..
这是最朴素的思路..加上树状数组..那就是优化查找该点位置的查找..初始化..a[1..n]都为1..则每次对c[i]求和的就是到该点前有多少个空位..
那如何通过c数组来找到我们需要的位置呢?...使用二分查找的方法..譬如现在要插入的这个人为(ki,xi)..那么我们就二分查找(ki--n)这个范围..因为他的位置至少不会小于ki..
我的方法不一定是很好的~~~2500MS..比较慢了..

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator