【NOIP提高A组模拟2018.8.14】 区间
2024-08-25 15:07:26
区间加:差分数组修改
O(n)扫描,负数位置单调不减
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue> using namespace std; inline int rd(){
int ret=,f=;char c;
while(c=getchar(),!isdigit(c))f=c=='-'?-:;
while(isdigit(c))ret=ret*+c-'',c=getchar();
return ret*f;
} const int MAXN=; int a[MAXN],d[MAXN];
queue<int> Q1,Q2;
int n,ans; int main(){
freopen("range.in","r",stdin);
freopen("range.out","w",stdout);
n=rd();
for(int i=;i<=n;i++) a[i]=rd();
for(int i=;i<=n;i++){
d[i]=a[i]-a[i-];
if(d[i]>) ans+=d[i];
}
d[n+]=-(<<);
printf("%d\n",ans);
int j=;
for(int i=;i<=n;i++){
if(d[i]==) continue;
while(d[i]!=){
if(d[j]>=){j++;continue;}
d[i]-=;
d[j]+=;
printf("%d %d\n",i,j-);
}
}
return ;
}
最新文章
- BootStrap的一个标准框架的内容解释——来源于bootstrap官网
- selenium support
- 烂泥:学习ubuntu之快速搭建LNMP环境
- fstream 中判断是否成功打开文件
- 在Windows驗證網站設定部分匿名存取
- JQuery动画插件Velocity.js发布:更快的动画切换速度
- CI_Autocomplete_2.0.php轻松实现Bebeans与Codeigniter的智能提示
- 快速学习bootstrap前台框架
- 关于css float 属性以及position:absolute 的区别。
- 基于Nodejs开发的web即时聊天工具
- css position relative obsolution
- Caused by: java.lang.ClassNotFoundException: org.springframework.orm.hibernate4.HibernateTemplate
- supergridcontrol记录,分页
- MVC5 Api Area 区域
- Java中常用的字节流和字符流
- java:取屏幕大小(去掉任务栏的高度部分)
- Java开源博客My-Blog之docker容器组件化修改
- LNMP分离式部署实例[转]
- django 使用多个数据库
- memset struct含有string的崩溃