小米9.5笔试

第二题，dp，d[i][j]表示前 i 个数的和能够凑成模完 x 为 j 的最小删除次数，那么最终答案加上最少的加1操作次数即可

const int N = 1e3 + 5;
int n,x;
int a[N];
int d[N][N];
void solve(){
    cin >> n >> x;
    for(int i = 1; i <= n; i++) cin >> a[i], a[i] %= x;
    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= x; j++) d[i][j] = 1e9;
    }
    d[0][0] = 0;
    for(int i = 1; i <= n; i++){
        for(int j = x - 1; j >= 0; j--){
            int res = (j - a[i] + x) % x;
            int h = min(d[i - 1][j] + 1, d[i - 1][res]);
            d[i][j] = min(d[i][j], h);
        }
    }
    int ans = 1e9;
    for(int i = 0; i <= x - 1; i++){
        if(i == 0){
            ans = min(ans, d[n][0]);
            continue;
        }
        ans = min(ans, d[n][i] + x - i);
    }
    cout << ans << endl;
}