P2234 [HNOI2002]营业额统计题解
统计 题解
2023-09-27 14:28:13 时间
一、双链表解法
1、需要记录原始数据\(a[i]\),索引\(i\):第几天,值:多少钱。
2、为了按金额排序,同时还需要记录相应的第几天,所以引入了结构体。
3、按结构体排序后的结果组成了一个双链表,本质上就是按金额从小到大排序的链,而链表中保存的数据是天数
,注意,是天数,而不是金额。就是哪一天排在哪一天后面。
4、倒着查找是本思路的精华。先从最后一天开始,根据上面的双链表,找出它的前驱和后继都是哪天,因为它是最后的一天,所以可以理解为找出的前驱和后继都是它前面的数字,这样,就可以直接计算了。
5、找出最后一天的最小波动值后,最后一天就没有存在的必要了,把它从链表中清除掉,防止后续的天计算时再错误的找到它。
6、总结一下本题的数据结构
(1)原始数据数组 \(a[N]\),描述:根据第几天,获取当天多少钱。
(2)结构体数组\(s[N]\),描述:按金额从小到大排序的数组,值为第几天。
(3)双链表,其实是对结构体数组的一个变形,因为如果直接使用结构体数组的话,有两个问题,一是不方便直接找出前驱和后继结点,二是不方便删除操作。有了双链表,这两个操作就方便多了。说白了,就是双链表用于维护动态数据很牛X,静态数组这方面不给力。
#include <bits/stdc++.h>
using namespace std;
const int N = 32768;
int ans;
//结构体:某一天
//money:营业额,day:第day天
struct node {
int money;
int day;
} s[N];
//结构体的比较函数,以钱小在前,钱大在后进行排序
bool cmp(node x, node y) {
return x.money < y.money;
}
//双链表的声明
int n, nex[N], pre[N], a[N];
int main() {
//输入
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i]; //原始数组,第1,2,3 ...天的营业额是多少
s[i] = {a[i], i}; //为了按营业额排序,但还需要保留是哪天的信息,没办法,只能使用结构体
}
//排序
sort(s + 1, s + 1 + n, cmp);//按金额由小到大排序
//"动态查找前驱后继",可以用链表的离线做法
//创建结构体+双链表,按金额排序后,日期的前后关系。
for (int i = 1; i <= n; i++) {
nex[s[i].day] = s[i + 1].day;
pre[s[i].day] = s[i - 1].day;
}
//从后向前,这个非常棒!这样的话,就可以无视前驱和后继的概念,不管是存在前驱还是后继,其实都是前面的日子金额,全可以用。
//用后最删除,不影响其它日期判断
for (int i = n; i >= 1; i--) {
//没有后继,有前驱
if (nex[i] == 0 && pre[i] > 0)ans += abs(a[i] - a[pre[i]]);
//没有前驱,有后继
else if (nex[i] > 0 && pre[i] == 0) ans += abs(a[i] - a[nex[i]]);
//有前驱有后继
else if (pre[i] > 0 && nex[i] > 0)ans += min(abs(a[nex[i]] - a[i]), abs(a[pre[i]] - a[i]));
//无前驱,无后继
else if (pre[i] == 0 && nex[i] == 0)ans += a[i];
//删除当前结点,防止前面的节点错误的找到它
nex[pre[i]] = nex[i];
pre[nex[i]] = pre[i];
}
//输出
cout << ans << endl;
return 0;
}
二、STL解法
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
set<int> s;//set 自带排序功能,强!set本身就是一种有序的容器。
int n, x, ans;
int main() {
//set中放入极大和极小值,这个放入极大与极小值的技巧太棒了,可以有效避免越界等问题,值得背诵~
s.insert(INF);
s.insert(-INF);
//读入
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> x;
//如果set是空,只有极大与极小值时.也就是第一个
if (s.size() == 2) {
ans += x;
s.insert(x);
} else {
//set居然支持二分法搜索~太棒了
//lower_bound() 函数用于在指定区域内查找不小于目标值的第一个元素
auto k = s.lower_bound(x);
//如果不相等时(相等就是零了,不需要加入)
if (*k != x) {
//复制出来迭代器
auto a = k;
//前驱
a--;
//最小波动值和
ans += min(abs(*a - x), abs(*k - x));
//金额入集合
s.insert(x);
}
}
}
//输出结果
cout << ans << endl;
return 0;
}
相关文章
- 为网站添加免费的访问计数统计和加入微博
- 统计每个文件关键字出现的个数
- 在JS中统计函数执行次数与执行时间
- 【原】web服务器占有量统计等 web网站
- php: 统计在线人数
- Python list去重及找出,统计重复项
- 2018-2019上海小区涨跌幅统计
- 【Python基础】字符串的基础操作:定义 || 统计 || 判断 || 查找和替换 || 大小写转换 || 文本对齐 || 去除空白字符 || 拆分和连接 || 字符串切片
- 五分钟教你如何优雅的统计代码耗时,让你知道你的程序到底慢在哪!
- Hadoop基础学习(一)分析、编写并执行WordCount词频统计程序
- 2180. 统计各位数字之和为偶数的整数个数
- 如何使用友盟统计(自定义事件)
- 【慕课网】如何统计序列中元素的出现频度
- 1021 个位数统计
- SHELL pv uv 统计事例
- 洛谷P1608 路径统计 题解
- 【ybt金牌导航5-1-1】【luogu P2590】树的统计