记录编号	577523	评测结果	AAAAAAAEAA
题目名称	1533.[HNOI 2002]营业额统计	最终得分	90
用户昵称	湖岸与夜与咸鱼	是否通过	未通过
代码语言	C++	运行时间	0.678 s
提交时间	2022-11-08 09:02:47	内存使用	5.54 MiB

// 河南省实验中学 高中 21级 关天泽

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define re register

const int INF = 0x3f3f3f3f;
using namespace std;

int n, a, b, sq;
bool k[550][2250], l[10050];
ll ans;

int main(){
	freopen("turnover.in", "r", stdin);
	freopen("turnover.out", "w", stdout);
	cin >> n;
	sq = 2250;
	cin >> a;
	k[a / sq + 1][a % sq] = 1;
	l[a / sq + 1] = 1;
	ans += a;
	n--; 
	while (n--){
		cin >> a;
		b = INF;
		int tk = a / sq + 1;
		bool fb = 0, fs = 0;
		for (int i = a % sq; i < sq; i++){
			if (k[tk][i] == 1){
				b = i - a % sq;
				fb = 1;
				break;
			}
		}
		if (fb != 1){
			for (int i = tk + 1; i <= sq + 1; i++){
				if (l[i] == 1){
					for (int j = 0; j < sq; j++){
						if (k[i][j] == 1){
							b = (i - tk) * sq + j - a % sq;
							break;
						} 
					}
					break;
				}
			}
		}
		for (int i = a % sq; i >= 0; i--){
			if (k[tk][i] == 1){
				b = min(a % sq - i, b);
				fs = 1;
				break;
			}
		}
		if (fs != 1){
			for (int i = tk - 1; i >= 0; i--){
				if (l[i] == 1){
					for (int j = sq - 1; j >= 0; j--){
						if (k[i][j] == 1){
							b = min((tk - i) * sq + a % sq - j, b);
							break;
						} 
					}
					break;
				}
			}
		}
		k[tk][a % sq] = 1;
		l[tk] = 1;
		ans += b;
//		cout << "b: " << b << " ans: " << ans << endl; 
	}
	cout << ans << endl;
	return 0;
}