次元传送门：洛谷P1315
思路
思路大概想到了 可是代码实现却没想到 所以参考题解了 D2T3的贪心果然有难度
我们考虑在每次用加速器有两种情况
到下一个点还需要等待：以后的时间就不再影响了到下一个点不需要等待：那么就会影响到后面的时间直到出现情况1（或者到最后一个点）
用sum[i]数组记录到i时的总人数 进行前缀和处理 e[i]为i可以影响到的最远的点
那么sum[i + e[i]] - sum[i] 即是能影响到的人数
这里需要用到贪心思想 即把影响最大的点用加速器
代码
#include<iostream>
#include<algorithm>
using namespace std;
#define maxn 10010
int n,m,k,ans;
int need[maxn],tim[maxn],
from[maxn],to[maxn],sum[maxn],last[maxn],mintime[maxn],e[maxn];
void fast(
int x)
{
while(x--)
//枚举加速器
{
e[n]=e[n-
1]=n;
//每次都初始化影响点
int now,Max=-
1;
//now为影响最大的点
for(
int i=n-
2;i>=
1;i--)
//从后面推回去
{
if(mintime[i+
1]<=last[i+
1]) e[i]=i+
1;
//如果要等待 最多影响到下一个
else e[i]=e[i+
1];
//如果不用等待 就会影响到后面的
}
for(
int i=
1;i<n;i++)
//枚举边
{
int temp=sum[e[i]]-sum[i];
//枚举影响
if(temp>Max&&need[i]>
0)
//找出最大影响和位置 并且时间要大于1
{
Max=
temp;
now=
i;
}
}
ans-=Max;
//答案减去影响到的人数
need[now]--;
//加速的时间减去
for(
int i=
2;i<=n;i++) mintime[i]=max(mintime[i-
1],last[i-
1])+need[i-
1];
//重新计算每个点的最短时间
}
}
int main()
{
cin>>n>>m>>
k;
for(
int i=
1;i<n;i++) cin>>
need[i];
for(
int i=
1;i<=m;i++
)
{
cin>>tim[i]>>
from[i]>>
to[i];
last[from[i]]=max(last[
from[i]],tim[i]);
//此点的最迟时间为每个人从此点出发的最小值
sum[to[i]]++;
//在to[i]下车的人数+1
}
mintime[1]=last[
1];
//第一个点初始化
for(
int i=
1;i<=n;i++) sum[i]+=sum[i-
1];
//前缀和
for(
int i=
2;i<=n;i++) mintime[i]=max(mintime[i-
1],last[i-
1])+need[i-
1];
//计算到达每个点所需要的最短时间
//最后一个人到前一个站点的时间和到这个点的时间取max
for(
int i=
1;i<=m;i++) ans+=mintime[to[i]]-tim[i];
//计算没有用加速器的答案 后面再减去用加速器的时间
fast(k);
//加速辣
cout<<
ans;
}
转载于:https://www.cnblogs.com/BrokenString/p/9886278.html
相关资源：JAVA上百实例源码以及开源项目
