05-08 11:34
  北京交通大学 Java  
Mike_f:第二题超时是因为你每次询问都要找最大值,这个操作是O(n). 
你可以用链表按顺序从大到小跟踪所有片段的大小,.每次你新进行一个分割,只需要将原节点替换为两个新节点,然后让这两个节点往后转移,直到满足降序就可以. 跟堆排的思想比较像
然后询问就变成O(1)了0 点赞 评论 收藏   
分享
 创作者周榜
更多 
 关注他的用户也关注了:
Mike_f:第二题超时是因为你每次询问都要找最大值,这个操作是O(n). 
你可以用链表按顺序从大到小跟踪所有片段的大小,.每次你新进行一个分割,只需要将原节点替换为两个新节点,然后让这两个节点往后转移,直到满足降序就可以. 跟堆排的思想比较像
然后询问就变成O(1)了