題目鏈接：點擊查看

題目大意：給出n個點代表n個面試者，每個點的點權代表每個面試者的能力值，現在老板要求將n個人分成m組，每組有n/m個人，多出來的余數的那些人舍棄掉了，現在要讓這m個組中的最大值相加，這個sum和需要滿足一個閾值k，現在求滿足上述條件的情況下，m的最小值是多少，也就是最少需要分多少個組

題目分析：首先這個題需要先判斷一下能否滿足條件，在輸入的時候維護一個sum和記錄一下所有人的能力之和，若sum比閾值k還小，那肯定是無法滿足條件的，直接輸出-1結束，若能滿足條件我們再枚舉m，因為實在沒有什么更好的辦法了，在枚舉m之前我們可以剪個枝，直接從1開始枚舉肯定是不合理的，我們先找一下n個人能力值中的最大值mmax，假設現在分成的m個組中，每個組的最大值都是這個mmax，那么最少也需要分成k/mmax個組，這樣一來比直接從1開始枚舉就減少了很多時間了，外層循環確定好組數后，內層循環確定一下每個組有多少個人，然后按照題意查詢每個組的最大值然后相加即可，注意一下，若想找每個組的最大值，暴力找肯定會T，我有想過用線段樹，但這畢竟是一個靜態最值查詢，而且給出的空間也足夠，所以可以直接上st表了，用在這里再合適不過了，配合上st表+暴力枚舉，就能把這個題拿下了

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=2e5+100;int n,k;int st[N][20],a[N];void get_st() {for(int i=1;i<=n;i++)st[i][0]=a[i];for(int i=1;i<=log2(n);i++)for(int j=1;j+(1<<i)-1<=n;j++)st[j][i]=max(st[j][i-1],st[j+(1<<i-1)][i-1]); }int query(int l,int r) {int k=log2(r-l+1);return max(st[l][k],st[r-(1<<k)+1][k]); }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);while(scanf("%d%d",&n,&k)!=EOF&&n!=-1){int sum=0;for(int i=1;i<=n;i++){scanf("%d",a+i);sum+=a[i];}if(sum<k){printf("-1\n");continue;}get_st();int mmax=*max_element(a+1,a+1+n);for(int i=k<mmax?1:k/mmax;;i++)//枚舉組數 {int num=n/i;//每組的人數int sum=0;for(int j=0;j<i;j++)sum+=query(j*num+1,(j+1)*num); if(sum>k){printf("%d\n",i);break;}}}return 0; }

?

總結

以上是生活随笔為你收集整理的HDU - 3486 Interviewe(RMQ-st表+暴力)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。