[AtCoder] Regular Contest 100-C

learningman 7月 01, 2018

C - Linear Approximation

Submit Record

Time limit : 2sec / Memory limit : 1024MB

Score : 300 points

Problem Statement

Snuke has an integer sequence A of length N.

He will freely choose an integer b.
Here, he will get sad if A_i and b+i are far from each other.
More specifically, the sadness of Snuke is calculated as follows:

  • abs(A_1 - (b+1)) + abs(A_2 - (b+2)) + ... + abs(A_N - (b+N))

Here, abs(x) is a function that returns the absolute value of x.

Find the minimum possible sadness of Snuke.


  • 1 ≤ N ≤ 2 * 10^5
  • 1 ≤ A_i ≤ 10^9
  • All values in input are integers.
  • Input

    Input is given from Standard Input in the following format:

    Input is given from Standard Input in the following format:

    NA_1 A_2 ... A_N


    Print the minimum possible sadness of Snuke.


    #include <bits/stdc++.h>using namespace std;long long n;long long number[100000001];bool compare(int a,int b){ return a>b;}long long getads(long long input_1,long long input_2){ if(input_1>input_2) return input_1-input_2; else return input_2-input_1;}long long getans(long long inputer){ long long answer=0; for(int j=1;j<=n;j++) { answer+=getads(number[j],number[inputer]); //printf("abs= %lld\n",getads(number[j],number[inputer])); //printf("answer is %lld\n",answer); } return answer;}int main(){ scanf("%lld",&n); for(int i=1;i<=n;i++) { long long tmp; scanf("%lld",&tmp); number[i]=tmp-i; //printf("number[%d]is% d\n",i,number[i]); } sort(number+1,number+n+1,compare); if(n%2==0) { printf("%lld",min(getans(n/2),getans(n/2+1))); } else { printf("%lld",getans(n/2+1)); } return 0;}

    本文采用 CC BY-NC-SA 3.0 协议进行许可,在您遵循此协议的情况下,可以自由共享与演绎本文章。

      1. learningman说道:


      2. learningman说道:

        test again

      3. learningman说道:



    电子邮件地址不会被公开。 必填项已用*标注

    you're currently offline