11036: 【原1036】二哥去取钱

题目

题目描述

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

Description

二哥来到一家银行。这家银行有3个柜台。二哥对银行的排队方式产生了兴趣。传统的排队方式是所有人都在柜台前排队，每个人进入银行后挑一个人数最少的队伍排上,要是人数一样，他会排那个柜台编号靠前的。

新的排队方式是每个人进入银行后只排一个队伍，一旦某个柜台有空，队伍最前的人就过去。

现在有\( N(N<100000) \) 个人在第0时刻里按照顺序进入了银行，并知道每个人的柜台占用时间。请计算两种排队方式下所有顾客等待时间的和及最后一个人处理完的时间。

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;

}