vectorwyx 的博客

vectorwyx 的博客

My left brain has nothing right, my right brain has nothing left.

题解 CF1471A 【Strange Partition】

posted on 2021-01-06 11:59:28 | under 题解 |

先从最简单的情况入手:数组中只有两个数 $a$ 和 $b$。

令 $a=cx+d,b=mx+k(0\le d,k < x )$。

  • $d,k$ 均为 $0$。不合并: $c+m$,合并: $c+m$
  • $d,k$ 有一个为 $0$。不合并: $c+m+1$,合并: $c+m+1$
  • $d,k$ 均不为 $0$,且 $d+k\le x$。不合并: $c+m+2$,合并: $c+m+1$
  • $d,k$ 均不为 $0$,且 $d+k>x$。不合并: $c+m+2$,合并: $c+m+2$

综上,把两个数合并后答案只可能减不可能增,因此一次都不合并时答案取得最大值,全部合并时答案取得最小值。

代码如下:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define ll long long
#define fo(i,x,y) for(register int i=x;i<=y;++i)
#define go(i,x,y) for(register int i=x;i>=y;--i)
using namespace std;

inline int read(){
    int x=0,fh=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-') fh=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    return x*fh;
}

const int N=1e5+5;
int a[N]; 

void work(){
    ll sum=0,mx=0;
    int n=read(),x=read();
    fo(i,1,n) a[i]=read(),sum+=a[i];
    fo(i,1,n){
        mx+=a[i]/x;
        if(a[i]%x) mx++;
    }
    printf("%lld %lld\n",sum/x+(bool)(sum%x),mx);
    //puts("");
}
int main(){
    int T=read();
    while(T--){
        work();
    }
    return 0;
}