抱歉,您的浏览器无法访问本站

本页面需要浏览器支持(启用)JavaScript


了解详情 >

P1732 序列

题意简述

一串数字,输出每个数字和前面与它最接近的数字的差之和。

输入:

  • 共有 $t$ 组数据。
  • 每行一个正整数 $n$,然后是 $n$ 个数字 $a_i \ldots a_n$。

输出:

  • 所有 $b_i$ 的和。
  • $b_i$ 为 $a_i$ 与之前某个数之差的绝对值的最小值。
  • 注意 $b_1=a_1$。

题目分析

不难想到暴力查找的做法,但我们发现在计算 $b_i$ 时需要消耗大量时间,所以需要进行优化。

二分查找可以节省很多时间,但前面的值不满足单调性,所以我们要使这些数满足单调性,可以存入priority queueset,但优先队列不好实现二分查找,而且这题可以忽略重复的数字,所以选用set

要注意对第一个数字进行特判,还要注意不要超出set范围。

详情请见代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>
using namespace std;
int t;
int n;
int ans;
int input;
set<int> s;
int main()
{
cin >> t;
while (t--)
{
/*初始化*/
s.clear();
ans = 0;

cin >> n;

/*由于只和前面的数字有关,所以可以在输入时就处理*/
for (int i = 1; i <= n; ++i)
{
cin >> input;
if (i == 1) //特判第一个数
{
s.insert(input);
ans += input;
continue;
}
set<int>::iterator tmp = s.lower_bound(input); //找到第一个大于等于当前数字的数
/*
如果tmp刚好等于当前数,那么tmp一定是最优的。
如果tmp大于了当前数,那么tmp后面的一定比tmp差
*/
if (tmp == s.end()) //当前的数字比之前的都大,没得选只能选最后一个
{
ans += abs(input - *(--tmp));
}
else if (tmp == s.begin()) //当前的数字比之前的都小,没得选只能选第一个
{
ans += abs(input - *(tmp));
}
else //选择tmp或tmp前一个
{
ans += min(abs(input - *(--tmp)), abs(input - *(tmp)));
}
s.insert(input); //将当前数字放入set
}
cout << ans << endl;
}
return 0;
}