题目链接:https://ac.nowcoder.com/acm/contest/40640/A
原题: 鸡尾酒要从 A 地去 B 地办 n 件事,其中第 i 件事耗时 a[i] 分钟,办完之后回到 A 地。但是如果他在 B 地连续待的时间大于等于 240 分钟,那么行程卡中就会显示他去过 B 地。根据 A 地的防控政策,如果去过 B 地,那么就会被隔离 7 天(10080 分钟),隔离之后才能继续正常行动(例如再启程去 B 地,或者在 A 地开始正常生活)。于是他有一个对策,即在 240 分钟快到的时候就从 B 地回到 A 地,然后再去 B 地,这样 240 分钟就会重新计时,从 A 地往返一趟 B 地耗时 400 分钟。现在他在 A 地准备出发,想要在 B 地办完所有事,回 A 地开始正常生活,办 n 件事的顺序无法打乱,且办每一件事的过程中无法打断。请问他至少需要多少分钟?
分析: 因为在每一件事的过程中都无法打断,且办 n 件事的顺序无法打乱,所以我们可以直接从 1~n 逐一枚举。如果出现 a[i] >= 240 就必须隔离,此时如果再往返就会浪费时间,所以可以直接办完所有事再回 A 地 (即1次来回) ,这样更节省时间。如果不存在 a[i] < 240 ,就直接用一个 sum 变量来存储本次的时间,如果 sum + a[i] > 240 的时候,直接回 A 地即可,更新 sum,然后再去办下一件事 (即多次来回) 。
代码如下:
#include <bits/stdc++.h>
using namespace std;
int a[1005];
int main()
{
int n;
cin >> n;
long long ans = 0, sum = 0, s = 0, c = 1;
bool f = 0; //判断是否存在 a[i] >= 240
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
if (a[i] >= 240) f = 1;
s += a[i];
}
for (int i = 1; !f && i <= n; i++)
{
if (sum + a[i] < 240)
{
sum += a[i];
}
else
{
sum = a[i];
c++;
}
} //不隔离 => 多次来回
if (s >= 240)
{
ans = s + 400 + 10080;
}
else
{
ans = s + 400;
}
if (!f && s + 400 * c < ans)
{
ans = s + 400 * c;
} //隔离 => 1次来回
printf("%d\n", ans);
return 0;
}