2021-10-13 T1 buy

题目描述

小 D 家附近新开了一家游乐园。小 D 经常光顾这家游乐园，他想要找到最优的购票方案。
小 D 想要进入游乐园 \(N\) 次，第 \(i\) 次在时刻 \(T_i\)，这个游乐园有两种购票方式：

1. 购买单次票：价格为 \(One\)，该票每张只能进入游乐园一次。

2. 购买时限票：时限票一共有 \(K\)? 种类型，第 \(i\)? 种类型的时限票可以使用的时长为 \(num_i\)?，
   价格为 \(cost_i\)?。具体来说，若一张时限票在第 t 时刻被使用，则在 \([t, t + num_i - 1]\)? 这个时刻区
   间内小 D 都可以进入游乐园。
   这两种票都可以购买任意多张。记 \(sum_i\)? 为小 D 前 \(i\)? 次进入游乐园的最小花费（不考虑
   第 \(i\)? 次之后的进入），小 D 定义第 \(i\)? 次进入游乐园的代价为 \(spend_i = sum_i - sum_{i- 1}\)?。小 D 想
   要知道每次进入游乐园的代价，即 \(spend_1\)?, ..., \(spend_n\)?。

数据范围及约定

对于前 \(10\%\) 的数据，\(K = 0\);
对于前 \(40\%\) 的数据，\(K\leq 2\), \(N\leq 10^3\);
对于前 \(60\%\) 的数据，\(K\leq 2\), \(N\leq 10^5\);
对于前 \(80\%\) 的数据，\(K\leq 30\), \(N\leq 10^5\);
对于 \(100\%\) 的数据，\(K\leq 500\), \(N\leq 10^5\), \(1\leq Ti, numi, costi, One\leq 10^9\)，\(T_i\) 单增。

题目分析

对于前 \(10\%\)? 的数据，每个时间点只能使用单次票，直接输出单次票价即可。

对于前 \(40\%\)? 的数据，枚举在每个时间点使用哪种票，显然以该时间点作为该票的时间区间终点最优。暴力向前寻找第一个不足以达到当前时间点的时间点，更新 \(sum_i\)? 即可，时间复杂度 \(O(kn^2)\)??。

memset(sum,0x7f,sizeof(sum));
sum[0] = 0;
for(int i = 1;i <= n;i++)
{
    for(int j = 0;j <= k;j++)
    {
        int pos = 0;
        for(int p = i - 1;p >= 1;p--)
        if(ti[p] + a[j].len-1 < ti[i]){pos = p;break;}
        sum[i] = min(sum[i],sum[pos] + a[j].pri);
    }
}
for(int i = 1;i <= n;i++)
    printf("%lld\n",sum[i] - sum[i-1]);

对于前 \(80\%\)的数据，考虑优化，在向前寻找第一个不足以到达当前点的时间点时，注意到答案位置显然具有单调性，二分即可，时间复杂度 \(O(knlogn)\)。

memset(sum,0x7f,sizeof(sum));
sum[0] = 0;
for(int i = 1;i <= n;i++)
{
    for(int j = 0;j <= k;j++)
    {
        int pos = 0,l = 0,r = i;
        while(r - l > 1)
        {
            int mid = (l + r) >> 1;
            if(ti[mid] + a[j].len - 1 < ti[i]) l = mid,pos = mid;
            else r = mid;
        }
        sum[i] = min(sum[i],sum[pos] + a[j].pri);
    }
}
for(int i = 1;i <= n;i++)
    printf("%lld\n",sum[i] - sum[i-1]);

对于 \(100\%\) 的数据，考虑进一步优化，注意到显然对于每一种票，第一个不足以到达当前时间点的位置随着时间点而递增，使用双指针的思想，对于每种票记录一个 \(pos_j\) 表示上一次的第一个位置，可保证指针前移只执行 \(kn\) 次，时间复杂度 \(O(kn)\)。

sum[0] = 0;
for(int i = 1;i <= n;i++)
{
    sum[i] = sum[i-1] + a[0].pri;
    for(int j = 1;j <= k;j++)
    {
        while(ti[pos[j]] + a[j].len - 1 < ti[i]) pos[j]++;
        sum[i] = min(sum[i],sum[pos[j]-1] + a[j].pri);
    }
}
for(int i = 1;i <= n;i++)
    printf("%lld\n",sum[i] - sum[i-1]);

附完整代码

#include
using namespace std;
typedef long long ll;
const int N = 100000 + 10;
struct node
{
    ll len,pri;
}a[N];
int n,k,pos[N];
ll ti[N];
ll sum[N];
signed main()
{
    freopen("buy.in","r",stdin);
    freopen("buy.out","w",stdout);
    scanf("%d%d",&n,&k);
    for(int i = 1;i <= n;i++)
        scanf("%lld",&ti[i]);
    for(int i = 1;i <= k;i++)
        scanf("%lld%lld",&a[i].len,&a[i].pri);
    scanf("%lld",&a[0].pri);
    if(k == 0)
    {
        for(int i = 1;i <= n;i++)
            printf("%lld\n",a[0].pri);
        return 0;
    }
    if(n <= 1000)
    {
        memset(sum,0x7f,sizeof(sum));
        sum[0] = 0;
        for(int i = 1;i <= n;i++)
        {
            for(int j = 0;j <= k;j++)
            {
                int pos = 0;
                for(int p = i - 1;p >= 1;p--)
                    if(ti[p] + a[j].len-1 < ti[i]){pos = p;break;}
                sum[i] = min(sum[i],sum[pos] + a[j].pri);
            }
        }
        for(int i = 1;i <= n;i++)
            printf("%lld\n",sum[i] - sum[i-1]);
        return 0;
    }
    if(k <= 30)
    {
        memset(sum,0x7f,sizeof(sum));
        sum[0] = 0;
        for(int i = 1;i <= n;i++)
        {
            for(int j = 0;j <= k;j++)
            {
                int pos = 0,l = 0,r = i;
                while(r - l > 1)
                {
                    int mid = (l + r) >> 1;
                    if(ti[mid] + a[j].len - 1 < ti[i]) l = mid,pos = mid;
                    else r = mid;
                }
                //cout << pos << endl;
                sum[i] = min(sum[i],sum[pos] + a[j].pri);
            }
        }
        for(int i = 1;i <= n;i++)
            printf("%lld\n",sum[i] - sum[i-1]);
        return 0;
    }
    sum[0] = 0;
    for(int i = 1;i <= n;i++)
    {
    	sum[i] = sum[i-1] + a[0].pri;
        for(int j = 1;j <= k;j++)
        {
            while(ti[pos[j]] + a[j].len - 1 < ti[i]) pos[j]++;
            sum[i] = min(sum[i],sum[pos[j]-1] + a[j].pri);
        }
    }
    for(int i = 1;i <= n;i++)
        printf("%lld\n",sum[i] - sum[i-1]);
    return 0;
}