# 11036: 【原1036】二哥去取钱

### 题目描述

author: 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1036

## Input Format

N，代表要进入银行的人数

a[1]...a[n]，a[i]代表第i个人要占用柜台的时间

## Output Format

W1 T1，分别代表老排队方式下所有顾客等待时间总和与最后一个人处理完的时刻

W2 T2，分别代表新排队方式下所有顾客等待时间总和与最后一个人处理完的时刻

## Sample Input

``````4
1 1 1 2
``````

## Sample Output

``````1 3
1 3
``````

## FineArtz's solution

``````/* 二哥去取钱 */
#include <iostream>
using namespace std;

int selectMin(int x, int y, int z){
int r = 1, m = x;
if (m > y){
r = 2;
m = y;
}
if (m > z){
r = 0;
m = z;
}
return r;
}

int main(){
int n;
int a[100005];
cin >> n;
long long w1 = 0, t1 = 0;
for (int i = 1; i <= n; ++i){
cin >> a[i];
}
int p[3] = {n / 3,
n / 3 + (n % 3 != 0 ? 1 : 0),
n / 3 + (n % 3 == 2 ? 1 : 0)};
long long t[3] = {0, 0, 0};
for (int i = 1; i <= n; ++i){
w1 += a[i] * (--p[i % 3]);
t[i % 3] += a[i];
}
t1 = max(t[0], max(t[1], t[2]));
cout << w1 << ' ' << t1 << endl;
long long w2 = 0, t2 = 0;
if (n == 1){
t2 = a[1];
}
else if (n == 2){
t2 = max(a[1], a[2]);
}
else{
int w[3] = {a[3], a[1], a[2]};
for (int i = 4; i <= n; ++i){
int j = selectMin(w[1], w[2], w[0]);
for (int k = 0; k < 3; ++k)
if (j != k)
w[k] -= w[j];
w2 += (n - i + 1) * w[j];
t2 += w[j];
w[j] = a[i];
}
t2 += max(w[0], max(w[1], w[2]));
}
cout << w2 << ' ' << t2 << endl;
return 0;
}
``````

## ligongzzz's solution

``````#include "iostream"
#include "algorithm"
using namespace std;

int main() {
int num;
cin >> num;
int *data = new int[num];

for (int i = 0; i < num; i++) {
cin >> data[i];
}

long long windows[3] = { 0 };
long long totalTime = 0, totalWaiting = 0;

//计算总时间
for (int i = 0; i < num; i++) {
totalWaiting += windows[i % 3];
windows[i % 3] += data[i];
}

totalTime = *max_element(windows, windows + 3);

cout << totalWaiting << " " << totalTime << endl;

totalTime = 0, totalWaiting = 0;

//新方法
long long newWindows[3] = { 0 };

for (int i = 0; i < num; i++) {
auto p = min_element(newWindows, newWindows + 3);
totalWaiting += *p;
//进入队列
*p += data[i];
}

totalTime = *max_element(newWindows, newWindows + 3);

cout << totalWaiting << " " << totalTime;

return 0;
}
``````

## Neight99's solution

``````#include <iostream>

using namespace std;

int minTime(long long *);
long long max(long long, long long, long long);

int main() {
int n;
long long *times;
long long w1, sum1, w2, sum2;
long long wait[3] = {0}, total[3] = {0};
cin >> n;

times = new long long[n];

for (int i = 0; i < n; i++) {
cin >> times[i];
}

//下面是第一种方法
for (int i = 0; i < n; i += 3) {
wait[0] += total[0];  //将已经过去的时间加入到该列队伍等待的总时间
total[0] += times[i];
}

for (int i = 1; i < n; i += 3) {
wait[1] += total[1];
total[1] += times[i];
}

for (int i = 2; i < n; i += 3) {
wait[2] += total[2];
total[2] += times[i];
}

w1 = wait[0] + wait[1] + wait[2];  //用户等待时间为三列队伍等待时间总和
sum1 = max(total[0], total[1],
total[2]);  //花费总时间为三列队伍里最费时间的那个

wait[0] = wait[1] = wait[2] = total[0] = total[1] = total[2] = 0;

//下面是第二种方法
for (int i = 0; i < n; i++) {
int k = minTime(total);
wait[k] += total[k];
total[k] += times[i];
}
w2 = wait[0] + wait[1] + wait[2];
sum2 = max(total[0], total[1], total[2]);

delete[] times;

cout << w1 << ' ' << sum1 << '\n' << w2 << ' ' << sum2;
}

int minTime(long long *x) {
if (x[0] <= x[1] && x[0] <= x[2]) {
return 0;
} else if (x[1] <= x[2]) {
return 1;
} else {
return 2;
}
}

long long max(long long x, long long y, long long z) {
if (x >= y && x >= z) {
return x;
} else if (y >= z) {
return y;
} else {
return z;
}
}
``````

## yyong119's solution

``````#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

int a[100005];
long long total[3], sum[3];

int getMinIndex() {

if (sum[0] <= sum[1] && sum[0] <= sum[2]) return 0;
else if (sum[1] <= sum[0] && sum[1] <= sum[2]) return 1;
else return 2;
}

int main() {

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

for (int i = 0; i < n; i += 3) {
total[0] += sum[0];
sum[0] += a[i];
}
for (int i = 1; i < n; i += 3) {
total[1] += sum[1];
sum[1] += a[i];
}
for (int i = 2; i < n; i += 3) {
total[2] += sum[2];
sum[2] += a[i];
}
long long totalTime = total[0] + total[1] + total[2];
long long maxTime = max(max(sum[0], sum[1]), sum[2]);
printf("%lld %lld\n", totalTime, maxTime);

for (int i = 0; i < 3; ++i) {
total[i] = 0; sum[i] = 0;
}
for (int i = 0; i < n; ++i) {
int k = getMinIndex();
total[k] += sum[k];
sum[k] += a[i];
}
totalTime = total[0] + total[1] + total[2];
maxTime = max(max(sum[0], sum[1]), sum[2]);
printf("%lld %lld\n", totalTime, maxTime);

return 0;

}
``````