题目链接:https://codeforces.com/problemset/problem/756/B
题目大意:

票价按以下方式构造。门票分为三种:
一张单程票要花20卢布,
一张90分钟的票需要50卢布,
一天(1440分钟)的票需要花费120卢布。

请注意,在时间t激活的x分钟的票证可用于从t到t  +  x  -1(含)范围内的旅行。假设所有行程仅花费一分钟。

为了简化乘客的选择,系统会自动选择最佳机票。每次行程开始后,系统会分析所有先前的行程和当前行程,并以最低的总成本为这些行程选择一组票证。假设涵盖从第一趟到目前的所有旅程的最低机票总费用为a,而之前收取的总金额为b。然后,系统向乘客收取a  -  b之和。

您必须编写一个程序,针对乘客进行的给定行程,计算每次行程后向乘客收取的费用总和。

思路:每次就3个选择。然后根据选择找到最优的转移(二分)

#include <bits/stdc++.h>
#define LL long long
using namespace std;
 
int n, a[100010], f[100010];
int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        scanf("%d", &a[i]);
    }
    for(int i=1; i<=n; i++){
        f[i]=f[i-1]+20;
        int p=(lower_bound(a+1, a+n+1, a[i]-89)-a-1);
        f[i]=min(f[i], f[p]+50);
        p=(lower_bound(a+1, a+n+1, a[i]-1439)-a-1);
        f[i]=min(f[i], f[p]+120);
        printf("%d\n", f[i]-f[i-1]);
    }
 
    return 0;
}