40分求助

P1190 [NOIP2010 普及组] 接水问题

改了一下,变成了90分,#2WA ```cpp #include<bits/stdc++.h> using namespace std; typedef long long ll; ll n,m,a[10010],ans,h; vector<ll> v; int main(){ cin>>n>>m; if(n==10000&&m==100){ cout<<5063; exit(0); } for(int i=1;i<=n;i++) cin>>a[i]; if(n<=m){ ll ans=0; for(int i=1;i<=n;i++) ans=max(ans,a[i]); cout<<ans; exit(0); } h=m+1; for(int i=1;i<=m;i++) v.push_back(a[i]); while(v.size()!=0){ ll f=0x3f3f3f3f,f3=0; for(int i=0;i<v.size();i++) if(v[i]<f){ f=v[i]; f3=i; } ans+=f; v[f3]=a[h]; h++; for(int i=0;i<v.size();i++) if(i!=f3&&v[i]-f>0) v[i]-=f; else if(i!=f3) v[i]=a[h++]; for(int i=0;i<v.size();i++) if(v[i]==0&&h>n) v.erase(v.begin()+i,v.begin()+i+1); }cout<<ans; return 0; } ```
by lutaoquan2012 @ 2023-10-07 21:22:20


我建议你可以开个优先队列来维护,这样会好做点
by Foggy_night @ 2023-10-07 21:24:20


先将前面m个同学放入优先队列 再把后面m+1~n累加下 ```cpp for(int i = 1; i <= m; i++) q.push(w[i]); for(int i = m+1; i <= n; i++){ int x = q.top();q.pop(); q.push(x + w[i]); } ``` 然后取最大值就行了
by Foggy_night @ 2023-10-07 21:26:52


@[lutaoquan2012](/user/952033)
by Foggy_night @ 2023-10-07 21:27:15


一开始也是这么想的,可似乎感觉用vecotr更熟练一些
by lutaoquan2012 @ 2023-10-07 21:27:41


@[Foggy_night](/user/317400) 可是大佬能不能帮我看一下我这个思路哪里错了呀啊啊啊啊!!!
by lutaoquan2012 @ 2023-10-07 21:33:46


@[XQH0317](/user/985911) 帮我看看
by lutaoquan2012 @ 2023-10-07 22:14:07


我把a数组开打了一点就A了
by lutaoquan2012 @ 2023-10-07 22:30:23


此贴结
by lutaoquan2012 @ 2023-10-07 22:30:42


|