Created
June 22, 2022 12:23
-
-
Save lyfer233/8da6e91e49318587c34d18c0a7b16160 to your computer and use it in GitHub Desktop.
My final solutions.cpp
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 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 | |
*/ |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment