Last active
June 22, 2022 05:59
-
-
Save lyfer233/7b79e3d069da698deccd00d97c6455f8 to your computer and use it in GitHub Desktop.
My solutions
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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 self_start[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 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()); | |
// 计算自有比率 | |
double tmp = 0.0; | |
if (near_person_id == person_id) tmp = fixed_money * self_factor[near_person_id] * (timestamp - self_start[near_person_id]); | |
else tmp = fixed_money * self_factor[near_person_id] * (timestamp - self_start[near_person_id] - 1); | |
interest[near_person_id] += tmp; | |
last_deposit_time[near_person_id] = timestamp - 1; | |
self_factor[person_id] = money[person_id] / now_deposit; | |
self_start[person_id] = timestamp; | |
if (near_person_id != person_id) { | |
if (last_deposit_time[person_id] == 0) { | |
last_deposit_time[person_id] = timestamp - 1; | |
} | |
// 计算当前用户从上一次存取款后到这次存取款的利息之和 | |
double delta = 0.0; // 除了当天之外的利息和 | |
if (timestamp - 1 >= last_deposit_time[person_id]) { | |
delta = sum[timestamp - 1] - sum[last_deposit_time[person_id]]; | |
// printf("timestamp is %d, last_deposit_time is %d", timestamp, last_deposit_time[person_id]); | |
} | |
double present_rate = money[person_id] / now_deposit; // 存取款后当天产生的利息 | |
interest[person_id] += (delta + present_rate) * fixed_money; | |
} | |
// Debug(); | |
// 更新相关信息 | |
last_deposit_time[person_id] = timestamp; | |
total_deposit = now_deposit; | |
near_person_id = person_id; | |
} | |
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()); | |
} | |
// Debug(); | |
// 计算当前用户从上一次存取款后到这次存取款的利息之和 | |
if (last_deposit_time[person_id] == 0) { | |
// 当还没有存款时,不需要计算利息 | |
interest[person_id] = 0.0; | |
} else { | |
if (near_person_id == person_id) { | |
interest[person_id] += self_factor[person_id] * (timestamp - self_start[person_id]) * fixed_money; | |
self_start[person_id] = timestamp; | |
last_deposit_time[person_id] = timestamp; | |
} else { | |
// cout << sum[timestamp] - sum[last_deposit_time[person_id]] << " " << sum[last_deposit_time[person_id]] << " " << self_factor[person_id] << endl; | |
interest[person_id] += (sum[timestamp] - sum[last_deposit_time[person_id]]) / factor[last_deposit_time[person_id]] * self_factor[person_id] * fixed_money; | |
} | |
} | |
double ans = interest[person_id]; | |
last_deposit_time[person_id] = timestamp; | |
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 | |
*/ |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment