算法
(模拟,枚举) $O(12)$
整个过程是确定的,从前往后依次模拟整个流程即可。
模拟过程中记录如下几个值:
total
: 存在妈妈那里的总钱数;remain
: 津津当前剩在自己手里的钱数;cur
:读入的值,表示当前这个月的生活开销;
依次枚举每个月,对于当前这个月,首先判断总共能拿到的钱数是否够用,即判断:
cur + 300 >= cur
是否成立;
如果够用,则将整百部分交给妈妈,自己剩下最多两位数的钱。
最后的总钱数是:total * 12 + remain
。
时间复杂度
依次将每个月处理一遍,所以总时间复杂度是 $O(12)$。
C++ 代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int total = 0, remain = 0;
for (int i = 1; i <= 12; i ++ )
{
int cur;
cin >> cur;
if (remain + 300 < cur)
{
total = -i;
break;
}
remain += 300 - cur;
total += remain / 100 * 120;
remain %= 100;
}
if (total >= 0) total += remain;
cout << total << endl;
return 0;
}