小米笔试0905

2

给一个长度为n的序列和一个整数x，每次操作可以选择序列中的一个元素，将其从序列中删去，或者将其值加一。问至少操作多少次，可以使操作后的序列(可以为空)中数字之和是x的倍数。

输入描述：第一行两个用空格限开的正整数n和x，含义如问题描述中所述。第二行是n个用空格醍开的正整数A[11,A[2]…A[n]，表示序列中n个元素的值。 $1<=n<=1000,1<=x<=1000,1<=A[]<=1000$

输出描述：一行一个整数，表示使序列中数字之和是x的倍数所需要的最少操作数。

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

int solve(vector<int>& a, int x) {
    int n = a.size();
    vector<vector<int>> dp(n + 1, vector<int>(x, INT_MAX / 2));
    dp[0][0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < x; j++) {
            // 选择删除当前元素
            dp[i][j] = min(dp[i][j], dp[i-1][j] + 1);

            // 选择保留当前元素
            int new_j = (j - a[i-1] % x + x) % x;
            dp[i][j] = min(dp[i][j], dp[i-1][new_j]);

            // 选择增加当前元素
            int next_j = (j + 1) % x;
            dp[i][next_j] = min(dp[i][next_j], dp[i][j] + 1);
        }
    }
    return dp[n][0];
}

int main() {
    int n, x;
    cin >> n >> x;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    cout << solve(a, x) << endl;
    return 0;
}