CF1223C Save the Nature

本文给出$O(nlog^2n)$和$O(nlogn)$的算法

首先二分答案的思路由询问内容的单调性可得，十分好想，一只log

重点在于check部分，有两种思路

1. 暴力sort两只log (156ms)

思维难度低，代码难度低

关键是出题人没来卡

先O(n)扫一遍，得到每天的贡献（百分比）

O(nlogn)从大到小排序，与每天的值配对

bool check(int n){
    int sum=0;
    for(int i=1;i<=n;i++){
        b[i]=0;
        if(i%al==0) b[i]+=x; //有第一种贡献
        if(i%be==0) b[i]+=y; //有第二种贡献
    }
    sort(b+1,b+1+n,greater<int>()); //greater<int>()是自带的一个比较函数，用来从大到小排
    for(int i=1;i<=n;i++) sum+=a[i]*b[i]; //a[]在main()中均已除以100，直接暴力配对
    return sum>=k;
}

2. lcm容斥一只log (62ms)

跑的飞快，毕竟正解

我们发现如果有贡献，只有三种情况，即a的倍数,b的倍数,lcm(a,b)的倍数

方便起见，先做这么一件事：

if(x<y) swap(x,y),swap(al,be);

这样就保证lcm优于a,a优于b了

用除法算出a,b,lcm各有几个记为xn,yn,xyn

由容斥原理可得xn,yn都要减去xyn

使得可以保证a,b,lcm贡献互不相交

然后分三段按照lcm(x+y),a(x),b(y)的顺序扫一遍即可

bool check(int n){
    int sum=0,xn=n/al,yn=n/be,xyn=n/lcm; //除法计算
    xn-=xyn; //容斥
    yn-=xyn;
    for(int i=1;i<=xyn;i++) sum+=(x+y)*a[i]; //lcm段
    for(int i=xyn+1;i<=xyn+xn;i++) sum+=x*a[i]; //a段
    for(int i=xyn+xn+1;i<=xyn+xn+yn;i++) sum+=y*a[i]; //b段
    return sum>=k;
}

代码

两只log

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    x=0;char c=getchar();bool f=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return x;
}
template<class t> inline void write(t x){
    if(x<0){putchar('-'),write(-x);}
    else{if(x>9)write(x/10);putchar('0'+x%10);}
}

#define int long long

const int N=2e5+5;
int q,n,a[N],b[N],k,x,y,be,al;

bool check(int n){
    int sum=0;
    for(int i=1;i<=n;i++){
        b[i]=0;
        if(i%al==0) b[i]+=x;
        if(i%be==0) b[i]+=y;
    }
    sort(b+1,b+1+n,greater<int>());
    for(int i=1;i<=n;i++) sum+=a[i]*b[i];
    return sum>=k;
}

void doit(){
    read(n);
    for(int i=1;i<=n;i++) read(a[i]),a[i]/=100;
    sort(a+1,a+1+n,greater<int>());
    read(x);read(al);
    read(y);read(be);
    read(k);
    int l=1,r=n,ans=-1;
    while(l<=r){
        int mid=l+r>>1;
        if(check(mid)) ans=mid,r=mid-1;
        else l=mid+1;
    }
    write(ans);puts("");
}

signed main(){
    read(q);
    while(q--) doit();
}

一只log

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    x=0;char c=getchar();bool f=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return x;
}
template<class t> inline void write(t x){
    if(x<0){putchar('-'),write(-x);}
    else{if(x>9)write(x/10);putchar('0'+x%10);}
}

#define int long long

const int N=2e5+5;
int q,n,a[N],b[N],k,x,y,be,al,lcm;

bool check(int n){
    int sum=0,xn=n/al,yn=n/be,xyn=n/lcm;
    xn-=xyn;
    yn-=xyn;
    for(int i=1;i<=xyn;i++) sum+=(x+y)*a[i];
    for(int i=xyn+1;i<=xyn+xn;i++) sum+=x*a[i];
    for(int i=xyn+xn+1;i<=xyn+xn+yn;i++) sum+=y*a[i];
    return sum>=k;
}

void doit(){
    read(n);
    for(int i=1;i<=n;i++) read(a[i]),a[i]/=100;
    sort(a+1,a+1+n,greater<int>());
    read(x);read(al);
    read(y);read(be);
    if(x<y) swap(x,y),swap(al,be);
    lcm=al*be/__gcd(al,be);
    read(k);
    int l=1,r=n,ans=-1;
    while(l<=r){
        int mid=l+r>>1;
        if(check(mid)) ans=mid,r=mid-1;
        else l=mid+1;
    }
    write(ans);puts("");
}

signed main(){
    read(q);
    while(q--) doit();
}
赏

fighter