2020-2021:teams:legal_string:jxm2001:contest:2020牛客国庆集训派对
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:contest:2020牛客国庆集训派对 [2020/10/07 21:13] jxm2001 |
2020-2021:teams:legal_string:jxm2001:contest:2020牛客国庆集训派对 [2020/10/07 21:26] (当前版本) jxm2001 [C、Expect to wait] |
||
|---|---|---|---|
| 行 254: | 行 254: | ||
| === 题意 === | === 题意 === | ||
| + | 给定 $n$ 个事件，时间分两种： | ||
| + | - $t$ 时刻有 $k$ 人借车 | ||
| + | - $t$ 时刻新加入 $k$ 辆车 | ||
| + | |||
| + | 接下来 $q$ 个询问，每次询问当初始时有 $b$ 辆车时所有人的等待时间和。 | ||
| === 题解 === | === 题解 === | ||
| + | |||
| + | 先假设初始时没有车，考虑根据初始事件构造“时间 $-$ 等待人数”图，则答案恰好为该图形围成的面积。 | ||
| + | |||
| + | 考虑初始时有 $b$ 辆车的情况，易知这等价于将图形向下移动 $b$ 个单位，同时删去小于 $0$ 的部分。 | ||
| + | |||
| + | 不难发现这同时等价于直线 $y=b$ 与原图形上方曲线围成面积。考虑将询问根据 $b$ 排序，利用扫描线法维护答案，时间复杂度 $O(n\log n)$。 | ||
| + | |||
| + | 需要注意无解情况的特判。另外发现也可以吉司机线段树区间置 $\max$ 再询问 $\text{sum}$ 无脑维护。 | ||
| + | |||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | const int MAXN=1e5+5; | ||
| + | struct Seg{ | ||
| + | int len,v; | ||
| + | bool operator < (const Seg &b)const{ | ||
| + | return v>b.v; | ||
| + | } | ||
| + | }seg[MAXN]; | ||
| + | struct Query{ | ||
| + | int v,idx; | ||
| + | bool operator < (const Query &b)const{ | ||
| + | return v>b.v; | ||
| + | } | ||
| + | }que[MAXN]; | ||
| + | LL ans[MAXN]; | ||
| + | int tim[MAXN],k[MAXN]; | ||
| + | int main() | ||
| + | { | ||
| + | int n=read_int(),q=read_int(); | ||
| + | _rep(i,1,n){ | ||
| + | char c=get_char(); | ||
| + | tim[i]=read_int(),k[i]=read_int(); | ||
| + | if(c=='+')k[i]=-k[i]; | ||
| + | } | ||
| + | int st=0; | ||
| + | _for(i,1,n){ | ||
| + | seg[i].len=tim[i+1]-tim[i]; | ||
| + | seg[i].v=st+=k[i]; | ||
| + | } | ||
| + | st+=k[n]; | ||
| + | st=max(0,st); | ||
| + | sort(seg+1,seg+n); | ||
| + | _for(i,0,q){ | ||
| + | que[i].v=read_int(); | ||
| + | que[i].idx=i; | ||
| + | } | ||
| + | sort(que,que+q); | ||
| + | int pos=1,slen=0; | ||
| + | LL sum=0; | ||
| + | _for(i,0,q){ | ||
| + | if(que[i].v<st){ | ||
| + | ans[que[i].idx]=-1; | ||
| + | continue; | ||
| + | } | ||
| + | if(i)sum+=1LL*(que[i-1].v-que[i].v)*slen; | ||
| + | while(pos<n&&que[i].v<seg[pos].v){ | ||
| + | slen+=seg[pos].len; | ||
| + | sum+=1LL*(seg[pos].v-que[i].v)*seg[pos].len; | ||
| + | pos++; | ||
| + | } | ||
| + | ans[que[i].idx]=sum; | ||
| + | } | ||
| + | _for(i,0,q){ | ||
| + | if(~ans[i]) | ||
| + | enter(ans[i]); | ||
| + | else | ||
| + | puts("INFINITY"); | ||
| + | } | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
2020-2021/teams/legal_string/jxm2001/contest/2020牛客国庆集训派对.1602076405.txt.gz · 最后更改: 2020/10/07 21:13 由 jxm2001
