非官方题解|挑战赛#21-T6

T6午枫的陪伴时间

• 官方辟谣

• 难度：普及+/提高 ？

• 思路分析

1. 准备阶段
   输入 $n$ 个选项的起始时间 $a_i$
   计算总礼物成本 $v$（所有 $v_i$ 之和）
   筛选出"可接受选项"（当 $v_i > cost_i$ 时）：
   结束时间$e_m = a_i+t-1$
   节省金额$s_m= v_i - cost_i$
2. 区间排序：
   对所有可接受选项按结束时间 $e_m$ 进行升序
   使用下表数组 ix[] 来保持原数组与排序后数组的关系
3. dp数组：
   初始化：dp[1] =第一个区间的节省值
   状态转移方程（递推是）：
   dp[i] = max(dp[i-1], s[i]+dp[j])
4. 结算：
   最优解 = 总礼物成本 $v -$ 最大节省金额 $dp_m$
   若无可接受选项 $(m=0)$ ，直接输出总礼物成本 $v$

• 通过代码

#include<bits/stdc++.h>
using namespace std;
int e[100010],s[100010];
int a[100010],ix[100010],es[100010]; 
long long dp[100010]; 
bool cp(int x,int y) {return e[x]<e[y];}//比较函数叫cmp在这题叫cp有自己的的道理
int main() {
    int n,t; 
    cin>>n>>t;
    for(int i=1;i<=n;i++) cin>>a[i]; 
    long long v=0;
    int m=0;    
    // 处理每个选项
    for(int i = 1; i <= n; i++) {
        int c, vi;
        cin>>c>>vi;//读取陪伴成本和礼物价格 
        v+=vi;//累计总礼物成本
        
        int si=vi-c;//节省
        if(si>0){//更划算
            m++;
            e[m]=a[i]+t-1;// 记录结束时间
            s[m]=si;//记录节省金额 
        }
    }   
 for(int i=1; i<=m; i++) ix[i]=i; 
    sort(ix+1,ix+m+1,cp); 
    if(!m){
        cout<<v<<endl;
        return 0;
    }
    for(int i=1;i<=m;i++)es[i]=e[ix[i]];
    //初始化
    dp[1]=s[ix[1]];
    
    for(int i=2;i<=m;i++) {
        int ce=es[i],cs=s[ix[i]];
        int tar=ce-t;//计算不重叠前驱地最晚结束时间
        int j=upper_bound(es+1,es+i,tar)-es-1;
        long long tmp=cs;
        if(j>=1)tmp+=dp[j];
        dp[i]=max(dp[i-1],tmp);
    }
    cout<<v-dp[m];
}

• 时间复杂度分析

$O(n+m~log~m)$