My final solutions.cpp

My final solutions.cpp

#include <iostream>
#include <vector>
#include <math.h>
using namespace std;

/*
我们假设总共有m个人参与了n笔交易,其中1 <= m <= 200000.
每笔交易的数据格式如下：
timestamp person_id operate amount
其中:
timestamp表示时间戳，以递增顺序出现.
person_id表示用户唯一标识id且persond_id <= m,
operate表示操作数，
    若operate = 0表示存款, 
    若operate = 1表示取款,
    若operate = 2表示查询并领取当前用户的未领取的收益.
*/

const double fixed_money = 100; // 固定奖金

vector<double> factor{1};       // 比率的前缀积
vector<double> sum{0};          // 比率的前缀积的前缀和

double money[200005];           // 当前用户账户的存款金额
double interest[200005];        // 当前用户未领取的收益之和
double total_deposit;           // 当前总存款数
int last_deposit_time[200005];  // 记录每个用户上次存取款的时间戳

double self_factor[200005];     // 自己的比率
int next_person_time[200005];   // 下一个用户的存款时间
int near_person_id;             // 最近一次订单的账户号

void Debug() {
    for (int i = 0; i < factor.size(); i++) {
        printf("factor[%d]: %.5f\n", i, factor[i]);
    }
    for (int i = 0; i < sum.size(); i++) {
        printf("sum[%d]: %.5f\n", i, sum[i]);
    }
    for (int i = 1; i <= 2; i++) {
        printf("interest[%d]: %.5f\n", i, interest[i]);
    }
}

void calculate_and_update(int timestamp, int person_id, double now_deposit) {

    if (near_person_id == person_id) {
        // 如果当前存款用户与上一个存款用户相同
        interest[person_id] += (sum[timestamp - 1] - sum[last_deposit_time[person_id]]) * fixed_money;
    } else {
        // 如果不同则需要分段处理

        // 第一段利息为自己的倍率*天数
        double first_interest = self_factor[person_id] * (next_person_time[person_id] - last_deposit_time[person_id] - 1);
        // 第二段为可以利用的倍率
        double second_interest = (sum[timestamp - 1] - sum[next_person_time[person_id] - 1]) / factor[last_deposit_time[person_id]] * self_factor[person_id]; 
        interest[person_id] += (first_interest + second_interest) * fixed_money;
    }

    // 更新当前用户倍率
    self_factor[person_id] = money[person_id] / now_deposit;
    // 更新当天的利息
    interest[person_id] += self_factor[person_id] * fixed_money; 

    // 更新相关信息
    last_deposit_time[person_id] = timestamp;
    next_person_time[near_person_id] = timestamp;
    total_deposit = now_deposit;
    near_person_id = person_id;

    // Debug();
}

void updateAccount(int timestamp, int person_id, double amount) {
    // 当账户余额不足时, 取款失败
    if (money[person_id] + amount < 0) {
        cout << "余额不足,取款失败" << endl;
        return;
    }
    money[person_id] += amount; // 修改当前账户存款金额
    double now_deposit = total_deposit + amount; // 当前所有用户的总存取款金额

    // 填充不连续的timestamp的空隙
    while (factor.size() < timestamp) {
        factor.push_back(factor.back());
        sum.push_back(sum.back() + factor.back());
    }

    // 计算当前timestamp的前缀积及前缀积的前缀和
    if (money[person_id] == now_deposit || fabs(total_deposit - 0.0) < 1e-6) {
        factor.push_back(1.0);
    } else {
        factor.push_back(factor.back() * (total_deposit / now_deposit));
    }
    sum.push_back(sum.back() + factor.back());

    
    if (last_deposit_time[person_id] == 0) {
        last_deposit_time[person_id] = timestamp - 1;
    }

    calculate_and_update(timestamp, person_id, now_deposit);

}

void deposit(int timestamp, int person_id, double amount) {
    updateAccount(timestamp, person_id, amount);
}

void withdraw(int timestamp, int person_id, double amount) {
    updateAccount(timestamp, person_id, -amount);
}

double claim(int timestamp, int person_id) {
    // 填充不连续的timestamp的空隙
    while (factor.size() <= timestamp) {
        factor.push_back(factor.back());
        sum.push_back(sum.back() + factor.back());
    }

    // 计算当前用户从上一次存取款后到这次存取款的利息之和
    if (last_deposit_time[person_id] == 0) {
        // 当还没有存款时，不需要计算利息
        return 0.0;
    }

    calculate_and_update(timestamp, person_id, total_deposit);
     
    double ans = interest[person_id];
    interest[person_id] = 0.0;
    return ans;
}

int main() {
    cout << "请按照timestamp person_id operate amount格式, 输入每笔交易" << endl;
    while (1) {
        // 读入每一笔交易并计算
        int timestamp, person_id, operate;
        cin >> timestamp >> person_id >> operate;
        if (operate == 2) {
            cout << "当前用户可领取的所有未领取收益为: " << claim(timestamp, person_id) << endl;
        } else {
            double amount;
            cin >> amount;
            if (operate == 0) deposit(timestamp, person_id, amount);
            else withdraw(timestamp, person_id, amount); 
        }
    }
    return 0;
}

/*
测试数据:
输入1:
1 1 0 1000.0
2 2 2
3 1 1 500.0
4 2 0 1000.0
5 1 2
6 2 2
期望输出1:
0
366.667
200
————————————————————————————————————————
输入2:
1 1 0 100
2 2 0 200
3 3 0 300
4 1 2
5 2 2
6 3 2
期望输出2:
166.67
166.67
200
————————————————————————————————————————
输入3:
1 1 0 100
3 2 0 200
3 1 2
4 2 2
5 1 0 300
6 1 2
6 2 2
期望输出:
233.333
133.333
166.666
66.67
————————————————————————————————————————
输入4:
1 1 0 100
2 2 0 100
3 3 0 100
5 1 0 100
7 2 0 100
9 3 0 100
10 1 2
10 2 2
10 3 2
期望输出:
463.333
313.333
223.333
————————————————————————————————————————
输入5:
1 1 0 100
2 2 0 200
3 1 2
4 2 2
5 1 2
期望输出5:
166.667
200
66.6667
————————————————————————————————————————
输入6:
1 1 0 100
2 1 2
3 2 0 100
4 3 0 100
5 2 2
6 1 2
7 1 1 100
8 1 2
9 3 2
期望输出6:
200
116.667
150
0
250
*/