链接

第一题

对价格从大到小进行排序，然后对下标取余，如果余数等于2，就不加上对应的值。

struct cmp {
    bool operator()(const int & lhs, const int & rhs) {
        return lhs > rhs;
    }
};
int main() {
    int N;
    cin >> N;
    vector<int> vec;
    int temp;
    for (int i = 0; i < N; ++i) {
        cin >> temp;
        vec.emplace_back(temp);
    }

    long long money = 0;
    sort(vec.begin(), vec.end(), cmp());
    for (int i = 0; i < N; ++i) {
        if (i % 3 != 2) {
            money += vec[i];
        }
    }
    cout << money << endl;

    return 0;
}

第二题

leetcode974原题。

• 先求前序和
• 然后对每个前序和取余，并用一个map存储余数出现的次数
• 对每个余数出现的次数，计算(n-1)*n/2，并累加

int main() {
    int N, M;
    vector<long long> vec;
    cin >> N;
    cin >> M;
    long long temp = 0;
    for (int i = 0; i < N; ++i) {
        cin >> temp;
        vec.emplace_back(temp);
    }
    int res = 0;
    vector<long long> prefix(N+1,0);
    for (int i = 0; i < N; ++i)
        prefix[i + 1] = prefix[i] + vec[i];

    vector<int> count(M,0);
    for (int i = 0; i < N + 1; ++i) {
        int temp = (prefix[i] % M + M) % M;
        ++count[temp];
    }
    for (int i = 0; i < M; ++i) {
        res += count[i] * (count[i] - 1) / 2;
    }
    cout << res << endl;
    return 0;
}

第三题

这题后面想到的，不知道是否正确，欢迎校正。

思路：

• 首先判断是否存在个数大于等于K的数字，如果存在直接输出
• 对0~9的每个数字进行判断
  • 如果个数大于0，然后判断变成K个该数字，需要的最小开销
  • 最后得到0~9中最小开销的数字
• 修改字符串，找到第一个字典序列

int main() {
    int N, K;
    cin >> N;
    cin >> K;
    vector<int> vec;
    map<int, int> m;
    string str;
    cin >> str;
    for (int i = 0; i < N; ++i) {
        ++m[str[i]-'0'];
    }

    for (int i = 0; i < 10; ++i) {
        if (m[i] >= K) { //如果存在满足需求的，即存在大于K个的数，直接输出
            cout << 0 << endl;
            cout << str << endl;
        }
    }

    //找出应该有K个的数，并得到消耗的能量
    int val = INT_MAX;
    int index = -1;
    for (int i = 0; i < 10; ++i) {
        if (m[i] == 0)
            continue;
        int left = i - 1, right = i + 1;
        int nums = K - m[i];
        int leftVal = 0, rightVal = 0;
        int leftNums = nums, rightNums = nums;
        while (nums > 0) {
            if (right < 10) {
                rightVal += (right - i) * (min(nums, m[right]));
                nums -= m[right];
                ++right;
            }
            if (nums > 0 && left >= 0) {
                leftVal += (i - left) * (min(nums, m[left]));
                nums -= m[left];
                --left;
            }
        }
        if (val > leftVal + rightVal) {
            val = leftVal + rightVal;
            index = i;
        }
    }

    //修改字符串，找到第一个字典序列
    int left = index - 1, right = index + 1;
    int nums = K - m[index];
    while (nums > 0) {
        if (right < 10 && m[right] > 0) {
            for (int i = 0; i < N; ++i) {
                if (str[i] - '0' ==  right) {
                    str[i] = '0' + index;
                    --nums;
                }
                if (nums == 0)
                    break;
            }
            ++right;
        }
        else if(right < 9) {
            ++right;
        }
        if (nums > 0 && left >= 0 && m[left] > 0) {
            for (int i = 0; i < N; ++i) {
                if (str[i] - '0' == left) {
                    str[i] = '0' + index;
                    --nums;
                }
                if (nums == 0)
                    break;
            }
            --left;
        }
        else if (nums >0 && left >= 1){
            --left;
        }
    }

    cout << val  << endl;
    cout << str << endl;
    return 0;    
}