Skip to content

14073: 【原4073】环式扶贫

题目

题目描述

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

Description

双十一之后贫窘卷土而来,本着团结友爱的精神,同学们展开了积极的扶贫互助行动。

假设每位同学会给出当前的经济状态M,当 M > 0 时代表尚有结余, M < 0 时代表出现赤字。并且假设N位同学以环状围坐,有结余的同学可以给予相邻的两位同学一定援助。

例如“ABCDA”四位同学, B可以帮助A、C但无法帮助到D。发生两个相邻同学的每一次互动均会使班级总援助次数加1.

已知所有同学的结余和赤字恰好相抵,求最少的援助次数使得所有同学收支平衡。

Input Format

第一行,一个整数 N。 (1 <= N <= 1e5) 第2行, 输出N个整数Mi。 (-1e9 <= Mi <= 1e9)

Output Format

一行,一个数,表示最少的班级总援助次数。

Sample Input1

4
1 2 3 -6

Sample Output1

3

Sample Input2

4
-1 0 1 0

Sample Output2

2

FineArtz's solution

/* 环式扶贫 */
#include <iostream>
#include <map>
using namespace std;

int main(){
    int n, t;
    long long sum = 0;
    map<long long, int> m;
    cin >> n;
    for (int i = 1; i <= n; ++i){
        cin >> t;
        sum += t;
        ++m[sum];
    }
    //for (auto i : m)
    //    cout << i.first << ' ' << i.second << endl;
    int cnt = 0;
    for (auto i : m){
        if (cnt < i.second) cnt = i.second;
    }
    cout << n - cnt << endl;
    return 0;
}

ligongzzz's solution

#include "iostream"
#include "cmath"
#include "cstdio"
#include "cstring"
using namespace std;

constexpr long long max_size = 2000009LL;

class node {
public:
    bool visited = false;
    long long key = 0;
    long long value = 0;
};

long long val_data[200009] = { 0 };
node hash_map[max_size];

int get_pos(long long key) {
    long long ans = (key + (long long)(1e12)) % max_size;
    for (;; ans = (ans + 1) % max_size) {
        if (hash_map[ans].visited) {
            if (hash_map[ans].key == key) {
                return ans;
            }
        }
        else {
            hash_map[ans].visited = true;
            hash_map[ans].key = key;
            return ans;
        }
    }
}

int main() {
    int n;
    scanf("%d", &n);

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

    long long ans = 0;
    //第一次循环
    long long cur_remain = val_data[0];
    for (int i = 0; i < n - 1; ++i) {
        ++hash_map[get_pos(cur_remain)].value;
        if (cur_remain)
            ++ans;
        cur_remain += val_data[i + 1];
    }

    //轮换
    long long cur_move = 0;
    for (int i = 0; i < n; ++i) {
        --hash_map[get_pos(val_data[i] + cur_move)].value;
        cur_move += val_data[i];
        ++hash_map[get_pos(-val_data[i] + cur_move)].value;
        long long cur_ans = n - 1 - hash_map[get_pos(cur_move)].value;
        ans = cur_ans < ans ? cur_ans : ans;
    }

    cout << ans;

    return 0;
}