【EOJ Monthly 2018.2 (Good bye 2017)】

 

【E. 出老千的 xjj】

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=3000000;
#define ll long long
int i,j,n,k,x;
ll p[maxn+10],sum[maxn+10],tmp,ans=100000000000000000,Max=0; 
int main()
{
    scanf("%d%d",&n,&k);
    for(i=1;i<=n;i++){
        scanf("%d",&x);
        tmp+=x;
        p[x]++;
    }
    if(tmp<=k){
        printf("0\n");
        return 0;
    }
    for(i=1;i<=maxn;i++) {
       sum[i]=sum[i-1]+p[i]*i;
       p[i]+=p[i-1];
    }
    for(i=2;i<=maxn;i++){
        ll yy=(k-1)/i+1;
        ll xx=n;
        tmp=0;
        //if(k%i==0&&yy<xx) continue;  
        if(k%i==0) continue; //上面的WA了 
        for(j=0;j<maxn/i;j++){
            int n1=(j+1)*i,n2=j*i+1;
            if(n2<0) n2=0;
            xx+=(p[n1]-p[n2-1]);
            tmp+=(p[n1]-p[n2-1])*((j+1)*i)-sum[n1]+sum[n2-1];
            if(k%i==0&&yy<xx) break;
            if(tmp>ans) break;
        }
        if((k%i==0&&xx<=yy)||k%i!=0){
          ans=min(ans,tmp);
        }
    }
    cout<<ans<<endl;;
    return 0;
}

 

關鍵詞:lt amp tmp maxn gt sum ans xx include< include

相關推薦:

Educational Codeforces Round 45 (Rated for Div. 2)

ZOJ Monthly, March 2018 題解

2016-2017 ACM-ICPC, Egyptian Collegiate Programming Contest (ECPC 16)

HAOI2018 [HAOI2018]染色 【組合數 + 容斥 + NTT】

bzoj 4566[Haoi2016]找相同字符 - 後綴數組 + 單調棧

FFT什麼的

春節比賽合集

BZOJ4555: [Tjoi2016&Heoi2016]求和

51nod1222 最小公倍數計數

2016-2017 ACM-ICPC Pacific Northwest Regional Contest (Div. 2) 題解