这个的思路就是让各个水龙头所用的时间尽可能地接近,可以先向优先队列中推入前m个数,由于开的是小根堆最小的数在前面我们把它拿出来,加上下一个人所需的时间。如此反复,直到都接完水,最大值就是答案。
#include<bits/stdc++.h> using namespace std; const int N=1e4+10; int n,m; int w[N]={0}; priority_queue<int,vector<int>,greater<int >> q; int cmp(int a,int b) { return a>b; } int main() { cin>>n>>m; for(int i=1;i<=n;i++) scanf("%d",&w[i]); // sort(w+1,w+1+n,cmp); // for(int i=1;i<=n;i++) printf("%d",w[i]); if(n<=m) { cout<<w[1]; return 0; } for(int i=1;i<=m;i++) { q.push(w[i]); // cout<<w[i]<<" "; } for(int i=m+1;i<=n;i++)//dfasdf { int t=q.top(); // cout<<q.top()<<" "; // if(i<=m) t+=w[i+m]; // else t+=w[i]; q.pop(); q.push(t); // cout<<"t:"<<t<<" "; } while(q.size()-1) q.pop(); // cout<<q.top()<<" ", cout<<q.top(); return 0; }
标签:接完,NOIP,int,1e4,PJT2,2010 From: https://www.cnblogs.com/wjk53233/p/16830078.html