洛谷 P4995 跳跳！

思路

贪心

从大到小排序，然后反复横跳，记录两个指针 \(l=1, r=n\)，从 \(1\) 跳到 \(n\)，再从 \(n\) 跳到 \(2\)，然后从 \(2\) 跳到 \(n - 1\)……，直到 \(l=r\) 结束，很容易证明这是正确的，因为每个位置的值互不相同且大于 \(0\)，所以要尽量使每次跳的差值最大，这样就能够保证获得的值最大

严谨的证明可以看这里：here

代码

/*

  Name: P4995 跳跳！

  Author: Loceaner

  Date: 31/08/20 20:14

  Description: 排序，然后反复横跳

*/

#include <cmath>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define int long long

using namespace std;

const int A = 1e5 + 11;

const int B = 1e6 + 11;

const int mod = 1e9 + 7;

const int inf = 0x3f3f3f3f;

inline int read() {

  char c = getchar();

  int x = 0, f = 1;

  for ( ; !isdigit(c); c = getchar()) if (c == '-') f = -1;

  for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);

  return x * f;

}

int n, a[A], ans;

bool cmp(int x, int y) {

  return x > y;

}

signed main() {

  n = read();

  for (int i = 1; i <= n; i++) a[i] = read();

  sort(a + 1, a + 1 + n, cmp);

  ans += a[1] * a[1];

  int l = 1, r = n, flag = 0;

  while (l < r) {

    if (!flag) {

      ans += (a[l] - a[r]) * (a[l] - a[r]);

      l++;

      flag = 1;

    }

    else {

      ans += (a[l] - a[r]) * (a[l] - a[r]);

      r--;

      flag = 0;

    }

  }

  cout << ans << '\n';

  return 0;

}

巴特西

洛谷 P4995 跳跳！

思路

代码

最新文章

热门文章