首页 > 其他分享 >洛谷-4552

洛谷-4552

时间:2022-11-11 20:11:06浏览次数:81  
标签:洛谷 int 差分 diff 正数 4552

洛谷-4552

思路

首先需要 由区间加减法或者最后的形式(变为1个数) 联想到 差分

在差分的形式下,只剩一个数意味着差分数组中\(2 \dots n\)都必须为0,其他任意。

而给我们的操作 在差分形式下 意味着 选择两个下标 一个加一,一个减一。

因此,我们很容易想到将\(2 \dots n\)的正数和负数分别统计,即\(z\)和\(f\),因此,最小操作数即为\(max(z,f)\)。

对于有多少种不同的数字,我们得先知道,为什么会产生不同的数字。可以发现,在将正数和负数成对消除后,剩下的全为正数,或者全为负数,在消除这些数时,有两种选择,因此会产生不同的数,所以不同的数字的个数就是\(abs(z-f) + 1\)。

Code

#include <bits/stdc++.h>
using namespace std;
#define _u_u_ ios::sync_with_stdio(false), cin.tie(nullptr)
#define cf int _o_o_;cin>>_o_o_;for (int Case = 1; Case <= _o_o_;Case++)
#define SZ(x) (int)(x.size())
inline void _A_A_();
signed main() {_A_A_();return 0;}

using ll = long long;
#define int long long
int mod = 1e9 + 7;
const int maxn = 2e5 + 10;
const int N = 210, M = 5010;
const int inf = 0x3f3f3f3f;

inline void _A_A_() {
    #ifdef LOCAL
    freopen("in.in", "r", stdin);
    #endif
    _u_u_;
    int n;
    cin >> n;
    vector<int> v(n + 1);
    vector<int> diff(n + 1);
    for (int i = 1;i <= n;i++) {
        cin >> v[i];
        diff[i] = v[i] - v[i - 1];
    }
    int z = 0, f = 0;
    for (int i = 2;i <= n;i++) {
        if (diff[i] > 0) z += diff[i];
        else f += -1 * diff[i];
    }
    cout << max(z,f) << "\n" << abs(z - f) + 1 << "\n";
}

标签:洛谷,int,差分,diff,正数,4552
From: https://www.cnblogs.com/FanWQ/p/16881619.html

相关文章

  • 洛谷刷题_质数口袋
    P5723【深基4.例13】质数口袋题目链接:https://www.luogu.com.cn/problem/P5723知识点:埃氏筛原理:要得到自然数n以内的全部素数,必须把不大于根号n的所有素数的倍数筛掉,......
  • 洛谷1923 排序
    洛谷1923错误这道题用的快排,但是非常卡时间,最后将快排优化,新学stl中nth_element(数组名,数组名+第k小元素,数组名+元素个数);将第k小元素找出,最后直接输出就行//判断k......
  • 洛谷B2079求出e的值
    解题思路:注意变量的类型就ok了,没什么不容易理解的地方#include<stdio.h>intmain(){doublenum=1,sum=1;longlongb=1,n;scanf("%d",&n);for(inti=1;i<=n......
  • 洛谷 P4423 [BJWC2011]最小三角形 题解
    求平面最近点对的时候有这样一种思路:将所有点全部绕原点旋转同一个角度,然后按横坐标排序。根据数学直觉,在随机旋转后,答案中的两个点在数组中肯定不会离得太远。把这种......
  • 洛谷刷题_ISBN 号码
    P1055[NOIP2008普及组]ISBN号码题目链接:https://www.luogu.com.cn/problem/P1055这道题从题意上来说还是比较简单的,刚开始想用整形直接输入一个一个数字,没有想到scan......
  • 洛谷刷题_三角形分类
    【深基3.习8】三角形分类题目描述给出三条线段a,b,c的长度,均是不大于10000的正整数。打算把这三条线段拼成一个三角形,它可以是什么三角形呢?如果三条线段不能组成一......
  • 洛谷B2078含k个三的数
    自行体会如果实在不会,就调试一下#include<stdio.h>intmain(){longintm;intn,k,num=0;scanf("%ld%d",&m,&k);for(inti=1;i<=15;i++){if(i=......
  • 洛谷-P3478 STA-Station
    STA-Station换根dp模板去到相邻的点可以根据去到的点的子树有多少个结点,来调整当前的值#include<iostream>#include<cstdio>#include<algorithm>#include<vecto......
  • 洛谷 [AGC021B] Holes 蓝 题解
    前言学校基础模拟赛的题,当时有思路但是不太会写凸包就没做,下来看了看,自己的思路大部分是正确的,有些细节没有想到,在此写篇题解。我用的是Andrew求凸包。思路答案为0......
  • 洛谷P1434滑雪分析
    [SHOI2002]滑雪题目描述Michael喜欢滑雪。这并不奇怪,因为滑雪的确很刺激。可是为了获得速度,滑的区域必须向下倾斜,而且当你滑到坡底,你不得不再次走上坡或者等待升降机来......