Nowcoder deco的abs

你的名字 2023-06-02 13:58 28阅读 0赞

[原题链接][Link 1]

## 题目描述 ##

deco最近迷上了abs，有一天他在梦里回忆起了自己以前见过的一道abs题目：  
给定一个长度为n的数列，第i个数字是aia\_iai，对于每个数字，你可以选择给他加上一个数d任意次，使得∑i=2n∣ai−ai−1∣\\sum\\limits\_\{i=2\}^n |a\_i-a\_\{i-1\}|i=2∑n∣ai−ai−1∣的值最小

可是当时deco非常的naive以至于他没做出来，现在他躺在床上玩手机不想起来拿电脑了，你可以帮他做出来吗？

## 输入描述: ##

第一行，两个数，n,d  
第二行，n个数，第i个数代表aia\_iai

## 输出描述: ##

一行，一个数，表示∑i=2n∣ai−ai−1∣\\sum\\limits\_\{i=2\}^n |a\_i-a\_\{i-1\}|i=2∑n∣ai−ai−1∣最小值

## 示例1 ##

### 输入 ###

4 3  
1 7 8 1

### 输出 ###

## 备注: ##

对于30%30%30%的数据，n≤105n \\leq 10^5n≤105  
对于50%50%50%的数据，n×d≤108n\\times d\\leq 10^8n×d≤108  
对于100%100%100%的数据，2≤n≤1072 \\leq n \\leq 10^72≤n≤107，1≤d≤100001\\leq d \\leq 100001≤d≤10000，1≤ai≤1061\\leq a\_i \\leq 10^61≤ai≤106

#include<cstdio>
    #define int long long
    using namespace std;
    typedef long long ll;
    
    inline void input(ll &x){
        ll ans=0,f=1;
        char c=getchar();
        while(c>'9'||c<'0'){
            if(c=='-')f=-1;
            c=getchar();
        }
        while(c>='0'&&c<='9'){
            ans=ans*10+c-48;
            c=getchar();
        }
        x=ans*f;
    }
    
    inline void output(ll x){
        if(x<0)x=-x,putchar('-');
        if(x>9)output(x/10);
        putchar(x%10+48);
    }
    
    inline void writeln(int x){
        output(x);
        putchar('\n');
    }
    
    inline int abs(int x){
        return x>0?x:-x;
    }
    
    inline int min(int a,int b){
        return a<b?a:b;
    }
    
    int n,d,x,last,ans;
    
    signed main(){
        input(n);input(d);
        for(int i=1;i<=n;i++){
            input(x);
            x%=d;
            if(i!=1)ans+=min(abs(x-last),d-abs(x-last));
            last=x;
        }
        writeln(ans);
    }

注意min中包含两种情况

至今未弄明白我的代码为什么不加读入优化离奇超时

以及为什么我的代码不开longlong离奇WA

可能我RP不好吧（

转载于:https://www.cnblogs.com/Y15BeTa/p/11404519.html

[Link 1]: https://ac.nowcoder.com/acm/contest/934/A