【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;
}

 

關鍵詞:if tmp maxn sum include xx ans ll for int

相關推薦:

hdu多校第二場dls題解 dls的搬運工

Kafka:ZK+Kafka+Spark Streaming集羣環境搭建(十)安裝hadoop2.9.0搭建HA

洛谷3934:Nephren Ruq Insania——題解

UVA 624 CD【01揹包+路徑記錄】

Round #4 RMQ問題ST算法

【模板】高精度運算

【TP3.2】TP3.2下實現ajax分頁(原創+親測可用)

江西財經大學第一屆進程設計競賽

Eigen庫筆記整理(一)

CF 922 思維貪心 變種揹包DP 質因數質數結論