【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

相關推薦:

狀壓DP(挑戰進程設計競賽)

[NOI2003][bzoj1507] 文本編輯器 editor [splay]

51nod1986 Jason曾不想做的數論題

BZOJ:2243: [SDOI2011]染色

bzoj千題計劃177:bzoj1858: [Scoi2010]串行操作

Codeforces Round #452 (Div. 2)

[Offer收割]編程練習賽39

樹鏈剖分