CodeForces - 948C(前缀和 + 二分)
2024-10-21 19:47:19
题意:N天,每天生产一堆雪体积 V[i] ,每天每堆雪融化 T[i],问每天融化了多少雪。
题解:对 T 求前缀和,求每一堆雪能熬过多少天,再记录一下多余的就行了。
#include <bits/stdc++.h>
using namespace std; const int maxn = 1e5 + ;
int N;
int V[maxn], T[maxn];
long long S[maxn], E[maxn], D[maxn], X[maxn]; int main()
{
scanf("%d", &N);
for(int i = ; i <= N; i++) scanf("%d", &V[i]);
for(int i = ; i <= N; i++) scanf("%d", &T[i]); for(int i = ; i <= N; i++) S[i] = S[i - ] + T[i];
for(int i = ; i <= N; i++){
int l = i, r = N;
while(l <= r){
int m = (l + r) >> ;
if(V[i] >= S[m] - S[i - ]) l = m + ;
else r = m - ;
} E[i]++; E[l]--;
D[l] += V[i] - (S[r] - S[i - ]);
}
for(int i = ; i <= N; i++) X[i] = X[i - ] + E[i]; for(int i = ; i <= N; i++) printf("%lld%c", X[i] * T[i] + D[i], i == N ? '\n' : ' '); return ;
}
最新文章
- mybatis学习
- SQL Server 2012 启动
- mysql之group_concat函数详解
- Hibernate入门5持久化对象关系和批量处理技术
- matlab processing for video
- android媒体文件扫描
- 通过UIBezierPath贝塞尔曲线画圆形、椭圆、矩形
- SpringMVC项目学习1_web.xml
- 【Web探索之旅】第三部分第一课:服务器
- Java多线程(二) —— 线程安全、线程同步、线程间通信(含面试题集)
- 阿里云 Angular 2 UI框架 NG-ZORRO介绍
- 【Codeforces 851D Arpa and a list of numbers】
- 设置元素text-overflow: ellipsis后引起的文本对齐问题
- zookeeper配置记录
- Power BI 与 Azure Analysis Services 的数据关联:1、建立 Azure Analysis Services服务
- Ubuntu 16.04下安装zsh和oh-my-zsh
- MySQL--7MySQL自定义函数
- create-react-app 知识点
- 深入理解java虚拟机---3垃圾回收机制GC
- poj Meteor Shower - 搜索
热门文章
- sqlite迁移mysql(导入导出数据)
- JavaScript中的Map和Set
- java使用JSCH连接FTP(Linux服务器)上传文件到Linux服务器
- SpringBoot非官方教程 | 第十九篇: 验证表单信息
- CentOS 7 下 Oracle 11g 安装教程
- 浅谈Java 8的新特性和使用场景
- mysql if...else 的使用
- vue中的$on,$emit,$once,$off源码实现
- echarts饼图扇区添加点击事件
- 我所用过的nginx的功能