CH-0304 IncDec Sequence
0304 IncDec Sequence 0x00「基本算法」例题
描述
给定一个长度为 n(n≤10^5 ) 的数列 {a_1,a_2,…,a_n},每次可以选择一个区间 [l,r],使下标在这个区间内的数都加一或者都减一。
求至少需要多少次操作才能使数列中的所有数都一样,并求出在保证最少次数的前提下,最终得到的数列可能有多少种。
输入格式
第一行一个正整数n。
接下来n行,每行一个整数,第i+1行的整数表示ai。
输出格式
第一行输出最少操作次数。
第二行输出最终能得到多少种结果。
样例输入
4
1
1
2
2
样例输出
1
2
数据范围与约定
- 对于100%的数据,n=100000,0<=ai<2147483648
来源
毕克,石家庄二中【Nescafé 22】杯NOIP模拟赛
OJ-ID:
ch-0304
author:
Caution_X
date of submission:
20191117
tags:
差分
description modelling:
给定长度为n的数组{a1,a2,......,an},每次可以选择区间[l,r]的所有元素加1或减1
问:至少需要多少次操作使得所有的数都相等,最终得到的数列可能有多少种
major steps to solve it:
(1)作差分数组b[](b[1]=a[1],b[n+1]=0)
(2)目标是使得b2,b3,.....,bn都为0,记p为b[]正数之和,q为b[]负数之和
(3)每一次对a进行的操作都相当于对b选择两个数分别进行+1和-1
(4)现在讨论b中选择地两个数bi,bj:
a)(2=<i,j<=n)
b)(i=1&&j<=n)
c)(i>=2&&j=n+1)
d)(i=1&&j=n+1)//d为无效操作,必不是最优解所进行的操作
(5)对于+1和-1操作,为了操作数最少,每次选择正数-1,负数+1,需进行操作min(p,q)
(6)当只有正数和负数时,还剩下|p-q|为配对,选择这些未配对的和b[0]或b[n+1]配对,需进行操作|p-q|,每一次操作都会得到一个新的b[0],所以最终数组个数为|p-q|+1
(7)综上:最少操作数:min(p,q)+|p-q|,最终数组种类|p-q|+1
AC code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[],b[];
int main()
{
ll n;
scanf("%lld",&n);
for(int i=;i<=n;i++)
{
scanf("%lld",&a[i]);
}
b[]=a[];
ll s0=,s1=;
for(int i=;i<=n;i++)
{
b[i]=a[i]-a[i-];
if(b[i]>) s0+=b[i];
else s1+=b[i];
}
s0=abs(s0);
s1=abs(s1);
b[n+]=;
ll ans0=min(s0,s1)+abs(s0-s1);
ll ans1=abs(s0-s1)+;
printf("%lld\n%lld\n",ans0,ans1);
return ;
}
最新文章
- Linux_安装软件包
- ups机制下停电提前关闭oracle数据库
- SpringMVC4 + Spring + MyBatis3 基于注解的最简配置
- jquery 中fadeIn,fadeOut动画
- Windows Phone开发(42):缓动动画
- Spring HTTPInvoker原理猜想(HTTP+序列化)
- MapReduce编程(一) Intellij Idea配置MapReduce编程环境
- mysql-冗余和重复索引
- Git综合使用命令行和gui工具小结
- 30行Python代码实现人脸检测
- Django 创建项目笔记
- bzoj 3999 线段树区间提取 有序链剖
- Replace 在动态sql中的实现
- centos7添加服务
- XCODE7 和IOS9适配后的一些问题
- BZOJ4698: Sdoi2008 Sandy的卡片(二分 hash)
- 三层架构,Struts2,SpringMVC实现原理图
- PowerDesigner 技巧【1】
- POJ1456 supermarket [堆]
- php-fpm使用
热门文章
- iOS 类别 类扩展 简要说明
- php5.4.16执行shell脚本
- 三、Vue 的一些语法样例
- Python Weekly 422
- SpringMVC生成的验证码图片不显示
- ImportError: No module named flask 导包失败,Python3重新安装Flask模块
- Maven项目使用mybatis报错 org.apache.ibatis.binding.BindingException: Invalid bound statement (not found):
- 互联网大厂Java面试题集—Spring boot面试题(一)
- spinand之data buffer
- Js实现回车登录,监听回车事件