超市促销 treap or hash

超市促销 treap or hash

突然发现几月前刷的此题

本着刷道水题的想法我就用treap虐了它一遍

题目描述： 
促销活动遵循以下原则：“参与本活动的顾客，应将自己的个人信息写在所付帐单背面，
并将账单投入指定的箱子。在每天的销售结束后，箱子中消费金额最大和最小的两张账单将
被选出。消费最多的顾客将得到一笔奖金，奖金的数目等于两张账单金额之差。为了避免因
为一次消费而得到多笔奖金，依照以上原则选出的两张账单将不会被放回到箱子中，但箱子
里剩下的账单可以继续参加第二天的活动。” 
你的任务是根据每天投入箱子的所有帐单，计算出整个促销活动中找是要付出的奖金总
额。本题中约定： 
1. 整个出销活动持续了 N 天，N≤5000。 
2. 第 i 天放入的钞票有 a[i]张，a[i]≤10^5，且 S=Σa[i]≤10^6。 
3. 第 i 天放入的钞票面值分别是 bi[1],bi[2],…,bi[a[i]]，b[j] ≤10^6。 
输入格式： 
输入文件的第一行的正整数 N 表示为此次促销活动持续的天数。接下来的 N 行含有一连
串用单个空格隔开的非负数。第 I+1 行的数字表示在第 I 天促销活动中放入投票箱内帐单的
价格。此行的第一个整数 K 表示这一天放入投票箱内的帐单数，接着的 K 个正整数分别代表
着每张帐单的价格。 
输出格式： 输出文件中恰含有一整数，它的值等于此次促销活动用作奖励的总花费。 
样例： 
pro.in： 
5 
3 1 2 3 
2 1 1 
4 10 5 5 1 
0 
1 2 
pro.out： 
19 

trep code

#include <ctime>
#include <cstdio>
#include <cstdlib>
#include <iostream>
using namespace std;
#define Rand() (rand () * rand () * rand () % 10000000)const int maxn = 1000000 + 5;class Treap_tree
{public :Treap_tree(){e = root = tot = 0;}void Left_Rotate(int &rt){int y = Right[rt];Right[rt] = Left[y];Left[y] = rt;rt = y;}void Right_Rotate(int &rt){int y = Left[rt];Left[rt] = Right[y];Right[y] = rt;rt = y;}void Insert(int &rt, int y){if (!rt){++e;Left[e] = Right[e] = 0;Fix[e] = Rand();Value[e] = y;rt = e;} else{if (y < Value[rt]){Insert(Left[rt], y);if (Fix[Left[rt]] > Fix[rt]) Right_Rotate(rt);} else if ( y >= Value[rt]){Insert(Right[rt], y);if (Fix[Right[rt]] > Fix[rt]) Left_Rotate(rt);}}}void Search_Max(int &rt){if (Right[rt])Search_Max(Right[rt]);else{MAX = Value[rt];rt = Left[rt];}}void Search_Min(int &rt){if (Left[rt])Search_Min(Left[rt]);else{MIN = Value[rt];rt = Right[rt];}}long long work(){cin >> n;for (int i=1; i<=n; ++i){int x, y;scanf("%d", &x);for (int j=1; j<=x; ++j){scanf("%d", &y);Insert(root, y);}Search_Max(root);if (!root) MIN = MAX;else Search_Min(root);tot += MAX - MIN;}return tot;}private :int MAX, MIN;int n, e, root;long long tot;int Left[maxn], Right[maxn], Fix[maxn], Value[maxn];
};
Treap_tree treap;int main()
{srand((unsigned)time(0));freopen("pro.in", "r", stdin);freopen("pro.out", "w", stdout);cout << treap.work();return 0;
}

其他的方法是hash or 分段hash

1.hash 复杂度是O(S + NM) M为最大数字

2.分段hash 复杂度O(S + N*M^(1/2))

分段hash是此题正解

但用hash我的数据也可AC

我的hash巧妙在每次操作记录了当前Min, Max;

读入时也适当更新

接着扫描则可优化较多了

hash code

#include <cmath>
#include <cstdio>
#include <climits>
#include <cstdlib>
#include <iostream>
using namespace std;
#define maxn 1000005int n;
int hash[maxn];
__int64 tot = 0;
int Min = INT_MAX, Max = -INT_MAX;int main()
{int x,y;freopen("pro.in", "r", stdin);freopen("pro.out", "w", stdout);scanf("%d", &n);for (int i=1; i<=n; i++){scanf("%d", &x);for (int j=1;j<=x;j++){scanf("%d",&y);++hash[y];Min = (Min > y) ? y : Min;Max = (Max < y) ? y : Max;}if (!hash[Max]){for (int j=Max-1; j>=1; --j)if (hash[j]) { Max=j; break; }}if (!hash[Min]){for (int j=Min+1; j<=maxn; ++j)if (hash[j]) { Min=j;break; }}tot += Max - Min;hash[Max]--; hash[Min]--;}printf("%I64d", tot);return 0;
}

数据奉上

=22451&uk=2652110486