为什么10分了
查看原帖
为什么10分了
315205
Kniqht楼主2022/10/1 18:27

有没有大佬帮忙看看,,,或者有曾经十分的大佬能说一下经验吗谢谢!

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
const int N=1e5+10;
int n,m,k,maxx[N];
int ans,s[N],d[N];
struct dis{
    int c,p;
}cnt[N];
struct Node{
    int t,x,y,gt;
}a[N];
vector<int> ed[N];
bool cmp(dis xx,dis yy){return xx.c>yy.c;}
bool cmp1(Node xx,Node yy){return xx.x<yy.x;}
int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<n;i++){
        scanf("%d",&s[i]);
        d[i]=s[i];
        s[i]+=s[i-1];
    }
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&a[i].t,&a[i].x,&a[i].y);
        maxx[a[i].x]=max(maxx[a[i].x],a[i].t);
        ed[a[i].y].push_back(i);
    }
    sort(a+1,a+m+1,cmp1);
    for(int i=1;i<n;i++){
        cnt[i].p=i;
        for(int j=1;j<=m;j++)
            if(a[i].x<=i-1&&a[i].y>=i) cnt[i].c++;
    }
    sort(cnt+1,cnt+n,cmp);
    for(int i=1;i<n;i++){
        if(!k) break;
        if(k>=d[cnt[i].p]){
            d[cnt[i].p]=0;
            k-=d[cnt[i].p];
            continue;
        }
        if(k<d[cnt[i].p]){
            d[cnt[i].p]-=k;
            break;
        }
    }
    // for(int i=1;i<n;i++) cout<<d[i]<<" ";
    // cout<<endl;
    int nowt=0,ans=0;
    for(int i=1;i<=n;i++){
        nowt+=d[i-1];
        // while(now<=m&&a[now].x==i){
        //     ans+=max(max(nowt,maxx[i])-a[now].t,0);
        //     a[now].gt=max(nowt,maxx[i]);
        //     now++;
        // }
        for(int j=0;j<ed[i].size();j++)
            ans+=(nowt-a[ed[i][j]].t);
        nowt=max(nowt,maxx[i]);
    }
    printf("%d",ans);
    return 0;
}
2022/10/1 18:27
加载中...