0,1≤xi,j≤100,1≤ti≤32767 ;
对于 40%的测试点, 1≤n≤100,∑ki≤100,1≤xi,j≤100,1≤ti≤86400 ;
对于 70%的测试点, 1≤n≤1000,∑ki≤3000,1≤xi,j≤1000,1≤ti≤109 ;
对于 100%的测试点, 1≤n≤105,∑ki≤3x105,1≤xi,j≤105,1≤ti≤109 。
沈笑夫一边做题,一边写解题报告:
“最早我看到这道题就用普通数组来存组这堆数据,一个一维数组存t,一个一维数组来存k。
但是,编了一半就发现了爆空间的问题,于是删掉它,用向量vector来编它,再定义一个ans数组存答案。
每一次计算出从这艘船开始向前一直找到超过86400秒的一艘船,删掉它们的内存,再从剩下的第一条船开始计算,统计(统计过程用桶排序式来),一直到目前的一条船。
代码如下:
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include