题解 AT4494 【Thumbnail】

· · 题解

ChungZH's blog · ChungZH's portfolio

Niwango-kun 是 Dwango Co.，Ltd. 的员工。 有一天，他被要求从用户提交的视频中生成缩略图。 要生成缩略图，他需要根据以下过程选择视频帧：

  • 获取整数 N 和 N 个整数 a_0,a_1,...,a_{N-1} 作为输入。N 表示视频的帧数，每个 a_i 表示视频的第 i 帧的表示
  • 选择第 t 个帧，其表示 a_t 最接近所有帧表示的平均值。

如果有多个这样的帧，请选择索引最小的帧。

找到他应选择生成缩略图的帧的索引 t。

简单地说就是求最接近 a 数组平均值的 a_t 的 t。

我们先求出它们的平均数，然后遍历 a 数组，找出最接近平均值的那个数的下标即可。时间复杂度应该是 O(N)。

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
double ave;
int main() {
  int n;
  int a[103];

  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
    ave += a[i];
  }

  ave /= n;
  int mini = 0;
  for (int i = 1; i < n; i++) {
    if (abs(a[i] - ave) < abs(a[mini] - ave)) mini = i;
  }

  cout << mini << endl;
  return 0;
}