题意: 有两个服务要求被满足, 服务 S1 要求 x1 数量的资源, S2 要求 x2 数量的资源. 有 n 个服务器来提供资源, 第 i 台能提供 a[i]的资源. 当你选择一定数量的服务器来为某个服务提供资源后, 资源需求会等量地分担给它们, 要求每台服务器承担的资源需求不超过其所能提供的资源需求. 给定一种合法的方案, 每台服务器要么没有被分配给任何一个服务, 或者被分配给其中一个服务.
对服务器按能提供的资源从小到大排序. 枚举给 S1 分配的服务器数量 i, 然后在 a 数组中二分, 就可以得到给 S1 提供的是哪 i 台服务器, 它们占据了 a 数组中连续的一段.
然后给 S2 哪些呢? 分两种情况:倘若 a 数组最后存在 k 台能满足 S2, 并且这 k 台不与给 S1 的相交, 那么不妨就给它这最后的 k 台.
倘若这 i 台之后, 不存在 a 的某个后缀能够满足 S2, 那么预处理一个东西: pre[i]代表 (n-i+1)-need[i](倘若要使用第 i 台那么至少要使用的总台数), 然后对这个玩意求个前缀 max, 如果 S1 的 i 台前存在某个位置 j, 能使得 pre[j]>=i, 就是说 j 所对应的能空出来的台数大于等于 S1 占据掉的台数, 那么不妨从第 n 台, 倒着数 need[j] 台(跳过 S1 的 i 台), 分配给 S2 即可.
- #include<cstdio>
- #include<algorithm>
- using namespace std;
- typedef long long ll;
- struct data{
- int val,pos;
- data(){}
- data(const int &val,const int &pos){
- this->val=val;
- this->pos=pos;
- }
- };
- bool cmp(const data &a,const data &b){
- return a.val!=b.val ? a.val<b.val : a.pos<b.pos;
- }
- int n,m1,m2;
- data a[300005];
- int premax[300005],premaxpos[300005],need[300005];
- int main(){
- //freopen("d.in","r",stdin);
- scanf("%d%d%d",&n,&m1,&m2);
- for(int i=1;i<=n;++i){
- scanf("%d",&a[i].val);
- a[i].pos=i;
- }
- sort(a+1,a+n+1,cmp);
- for(int i=1;i<=n;++i){
- int tmp;
- if(m2%a[i].val==0){
- tmp=m2/a[i].val;
- }
- else{
- tmp=m2/a[i].val+1;
- }
- if((n-i+1)-tmp>premax[i-1]){
- premax[i]=(n-i+1)-tmp;
- premaxpos[i]=i;
- need[i]=tmp;
- }
- else{
- premax[i]=premax[i-1];
- premaxpos[i]=premaxpos[i-1];
- need[i]=need[i-1];
- }
- }
- int hou=0;
- for(int i=n;i>=1;--i){
- if(m2<=(ll)a[i].val*(ll)(n-i+1)){
- hou=i;
- break;
- }
- }
- if(!hou){
- puts("No");
- return 0;
- }
- for(int i=1;i<=n;++i){
- int tmp;
- if(m1%i==0){
- tmp=m1/i;
- }
- else{
- tmp=m1/i+1;
- }
- data *p=lower_bound(a+1,a+n+1,data(tmp,0),cmp);
- if(p-a+i-1>n){
- continue;
- }
- if(hou>=p-a+i){
- puts("Yes");
- printf("%d %d\n",i,n-hou+1);
- for(int j=p-a;j<p-a+i;++j){
- printf("%d%c",a[j].pos,j==p-a+i-1 ? '\n' : ' ');
- }
- for(int j=hou;j<=n;++j){
- printf("%d%c",a[j].pos,j==n ? '\n' : ' ');
- }
- return 0;
- }
- else if(premax[p-a-1]>=i){
- puts("Yes");
- printf("%d %d\n",i,need[p-a-1]);
- for(int j=p-a;j<p-a+i;++j){
- printf("%d%c",a[j].pos,j==p-a+i-1 ? '\n' : ' ');
- }
- int cnt=0;
- for(int j=n;j>=1;--j){
- if(j>=p-a && j<p-a+i){
- continue;
- }
- ++cnt;
- printf("%d%c",a[j].pos,cnt==need[p-a-1] ? '\n' : ' ');
- if(cnt==need[p-a-1]){
- break;
- }
- }
- return 0;
- }
- }
- puts("No");
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2582242.html