思路:标记出每一段路会被多少个人经过,然后将经过人数最多的几条路用氮气加速,做完这些模拟一遍求出答案,
by Kniqht @ 2022-10-01 18:29:27
你这和我一样
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m,k,d[1001],tx[1001],ty[1001];
long long ans;
struct tour
{
int t,x,y;
}a[10010];
struct pers
{
int id,num,b;
}f[1001];
bool cmp(pers x,pers y){return x.num>y.num;}
int main()
{
//freopen("bus.in","r",stdin);
freopen("bus.out","w",stdout);
ios::sync_with_stdio(false);
cin>>n>>m>>k;
for(int i=1;i<n;i++)
cin>>d[i];
for(int i=1;i<=m;i++)
{
cin>>a[i].t>>a[i].x>>a[i].y;
for(int j=a[i].x;j<a[i].y;j++)
f[j].num++;
tx[a[i].x]=max(tx[a[i].x],a[i].t);
}
for(int i=2;i<=n;i++)
{
ty[i]=max(ty[i-1],tx[i-1])+d[i-1];//ty到达时间, tx出发时间
f[i-1].b=ty[i]-tx[i];//计算可以被加速的有效成分
f[i-1].id=i-1;
}
sort(f+1,f+n,cmp);
for(int i=1;i<n;i++)
{
int j=f[i].id;
if(f[j].b<=0)continue;
if(f[j].b>=k)
{
d[j]-=k;
break;
}
else
d[j]-=f[j].b;
k-=f[j].b;
}
memset(tx,0,sizeof(tx));
for(int i=1;i<=m;i++)
tx[a[i].x]=max(tx[a[i].x],a[i].t);
for(int i=2;i<=n;i++)
ty[i]=max(ty[i-1],tx[i-1])+d[i-1];
for(int i=1;i<=m;i++)
ans+=ty[a[i].y]-a[i].t;
cout<<ans;
return 0;
}
``````
by oulii @ 2023-10-12 20:21:43