bzoj3043IncDec Sequence*
2024-08-31 20:57:30
题意:
n个数,每次可以将区间l到r里的数+1或-1,问将它们变成同个数的最小操作次数和保证最小操作次数前提下有多少中可能。n≤100000。
题解:
先对原数组差分(得到的数组第一个为原数组第一个元素,之后的元素为原数组相邻元素之差),则原操作变为左右端点对应元素加1减1或减1加1,求最小操作次数使得除第一个元素之外剩下元素均为0。则先将正负数对消,剩下的数可以自己消掉或与第一个数对消,故第一问答案为max(正数之和,负数绝对值之和) 第二问答案为abs(正数之和-负数绝对值之和)+1。
代码:
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 100010
#define ll long long
using namespace std; inline ll read(){
char ch=getchar(); ll f=,x=;
while(ch<''||ch>''){if(ch=='-')f=-; ch=getchar();}
while(ch>=''&&ch<='')x=x*+ch-'',ch=getchar();
return f*x;
}
int n; ll day,xiy,a,b;
int main(){
n=read(); a=read(); inc(i,,n){b=read(); if(b-a>)day+=(b-a);else xiy+=(a-b); a=b;}
printf("%lld\n%lld",max(day,xiy),abs(day-xiy)+); return ;
}
20160929
最新文章
- spider RPC框架的需求来源与特性介绍(一)
- Windows phone 全景视图
- O2O、C2C、B2B、B2C的区别
- tomcat、Linux服务器
- 3D语音天气球(源码分享)——完结篇
- Linux 下WordPress FTP帐号解决办法
- Maven 的41种骨架
- 第十周java 学习总结
- mysql关于列转行的想法,以及列求乘集
- nopCommerce添加支付插件
- POJ 2127 Greatest Common Increasing Subsequence -- 动态规划
- Apache MINA 框架之默认session管理类实现
- 【转】	UIView如何管理它的子视图
- cf Perfect Pair
- javascript 事件代理及应用
- The OpenGL pipeline
- AWT与Swing的区别
- 2018-2019-1 20165318 20165326 实验五 通讯协议设计.md
- day12-集合
- gf框架之grpool - 高性能的goroutine池
热门文章
- 2019-02-15 python接口图灵机器人(简单好玩)
- 果然学习好是有道理的,学习Mysql与正则表达式笔记
- cb44a_c++_STL_算法_删除_(2)remove_copy_remove_copy_if
- Beta冲刺<;5/10>;
- 挖洞入门_显错型SQL注入
- 在执行jar包时如何使用调优参数
- 谁再悄咪咪的吃掉异常,我上去就是一 JIO
- vue全家桶(4.3)
- JavaScript基础对象创建模式之声明依赖模式(023)
- JavaScript基础Literal 与 Constructor(008)