題目鏈接：點擊查看
題目大意：給出 n 個機器，每個機器可以處理 a[ i ] 的工作，現在有兩個工作需要處理，工作量分別為 x1 和 x2，可以將一個工作分配給 k 個機器同時完成，需要滿足：
k 個機器都需要滿足 每個機器只能處理一個工作
題目要求輸出一種合適的構造方案，如果無解輸出 No
題目分析：首先預處理出 a[ i ] 和 b[ i ] ，分別代表將 x1 和 x2 分配給 i 個機器所需要的最低下限
然后設題目中的 a[ i ] 為 c[ i ] （避免與上面的兩個變量重名），代表的就是機器 i 的最大工作上限
不難看出假如對 c 數組非降排序后，需要分配的機器實質上是兩段連續的區間，一段為中綴，另一段為后綴，我們只需要找到這樣兩段沒有交集的區間滿足就是一組可行解了
貪心去想的話，為了使得這兩個區間不存在交集，那么后綴開始的位置顯然是越靠后越優，這個可以從后向前掃一遍找出最短的那個滿足條件的后綴
而對于中綴來說，既要確定位置又要確定長度，不過不難發現如果確定了中綴的長度后，可以二分找到中綴的起止位置，所以做法就呼之欲出了
我們可以在確定最短的后綴的情況下，去枚舉中綴可能的長度，然后二分找到其位置，每次檢查一下兩段區間是否存在交集即可
需要注意的是，需要做兩次這樣的算法，因為可能中綴代表的是 x1，后綴代表的是 x2，也可能中綴代表的是 x2，后綴代表的是 x1
代碼：
?
//#pragma GCC optimize(2)
//#pragma GCC optimize("Ofast","inline","-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#include<bitset>
#include<unordered_map>
using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e6+100;int n,x1,x2,a[N],b[N],c[N],id[N];void solve1()
{int pos=-1;for(int i=n;i>=1;i--)//找到對于x2滿足條件的最短后綴if(c[i]>=b[n-i+1]){pos=i;break;}for(int i=1;i<n;i++)//枚舉x1需要分配的長度 {int l=lower_bound(c+1,c+1+n,a[i])-c;//起止位置int r=l+i-1;if(r<pos)//如果不存在交集，說明存在解{puts("Yes");printf("%d %d\n",r-l+1,n-pos+1);for(int i=l;i<=r;i++)printf("%d ",id[i]);puts("");for(int i=pos;i<=n;i++)printf("%d ",id[i]);puts("");exit(0);}}
}void solve2()
{int pos=-1;for(int i=n;i>=1;i--)//找到對于x1滿足條件的最短后綴if(c[i]>=a[n-i+1]){pos=i;break;}for(int i=1;i<n;i++)//枚舉x2需要分配的長度 {int l=lower_bound(c+1,c+1+n,b[i])-c;int r=l+i-1;if(r<pos)//同上同上{puts("Yes");printf("%d %d\n",n-pos+1,r-l+1);for(int i=pos;i<=n;i++)printf("%d ",id[i]);puts("");for(int i=l;i<=r;i++)printf("%d ",id[i]);puts("");exit(0);}}
}int main()
{
#ifndef ONLINE_JUDGE
// freopen("data.in.txt","r",stdin);
// freopen("data.out.txt","w",stdout);
#endif
// ios::sync_with_stdio(false);scanf("%d%d%d",&n,&x1,&x2);for(int i=1;i<=n;i++){scanf("%d",c+i);id[i]=i;a[i]=(x1+i-1)/i;b[i]=(x2+i-1)/i;}sort(id+1,id+1+n,[&](int a,int b){return c[a]<c[b];});sort(c+1,c+1+n);solve1();solve2();puts("No");return 0;
}
?
?
總結
以上是生活随笔為你收集整理的CodeForces - 967D Resource Distribution(贪心+二分+构造)的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
