F - To Add Which?
Description
There is an integer sequence with
N integers. You can use 1 unit of cost to increase any integer in the sequence by 1.
Could you tell us the least units of cost to achieve that, the absolute value of difference between any two adjacent integers is not more than
D?
Input
The first line has one integer
T, means there are T test cases.
For each test case, the first line has two integers N, D (1 <=
N <= 105, 0 <= D < 109), which have the same meaning as above. The next line has
N integers describing the sequence. Every integer in this sequence is in range [0, 109).
The size of the input file will not exceed 5MB.
Output
For each test case, print an integer in one line, indicates the desired answer.
Sample Input
3
5 2
1 3 5 3 5
5 1
1 2 3 5 6
5 2
1 7 3 5 9
Sample Output
0
3
8
数据比较水，n^2也能过，有nlogn的算法，要用线段树和递归，暂时不会写。。。
#include<stdio.h>
#include<math.h>
long long a[100005];
int main()
{
int T,i,j;
long long n,m,sum;
scanf("%d",&T);
while(T--)
{
scanf("%lld%lld",&n,&m);
sum=0;
for(i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
}
for(i=2;i<=n;i++)
{
if(fabs(a[i]-a[i-1])<=m )
continue;
else if(a[i]<a[i-1])
{
sum=sum+a[i-1]-m-a[i];
a[i]=a[i-1]-m;
}
else if(a[i]>a[i-1])
{
sum=sum+a[i]-m-a[i-1];
a[i-1]=a[i]-m;
for(j=i-1;j>=2;j--)
{
if(fabs(a[j]-a[j-1])<=m )
break;
if(a[j]>a[j-1])
{
sum=sum+a[j]-m-a[j-1];
a[j-1]=a[j]-m;
}
}
}
}
printf("%lld\n",sum);
}
}最新文章
- 程序员DNS知识指南
- Java观察者设计模式
- DAY7L2【C001】
- HTTP基础02--HTTP协议简介
- is_user_logged_in()
- VBS基础篇 - 内置函数
- 选择——ERP信息系统选型
- 存储过程往拼接的sql语句中传递日期值
- 当使用VS CODE 时，如果窗口中打开的文件无法识别HTML的话，可以使用以下方法添加要识别的文件类型
- python学习笔记--Django入门一 网页显示时间
- Windows7のping応答の設定
- mobile web曾经的踩过坑
- C#中静态与非静态方法比较【转】
- NoSQL的价值到底在哪里？
- ListView下拉刷新及上拉更多两种状态
- Java 抽象工厂模式
- JS框架设计读书笔记之-选择器引擎01
- C#开源项目大全
- 新版本grafana添加数据源报错！
- python 笔记数据类型