A小柒与啦啦啦的博弈

链接：https://ac.nowcoder.com/acm/contest/111921/A

由于轮流选取宝物，每次选取都争取最大利益化。小柒先手，难道是贪心算法？ 简单来说就是选取剩下宝物中价值最大的宝物。直接将宝物价值按升序排列，再由两人按顺序累加即可。
主要是数据会爆 int ,选择 long long 即可。

Code

#include<stdio.h>
int com(const void *a, const void *b) {
    return *(int*)b - *(int*)a;
}
int main() {
    int n;
    scanf("%d", &n);
    int* num = malloc(sizeof(int) * n);
    for(int i = 0; i < n; i++) {
        scanf("%d", &num[i]);
    }
    qsort(num, n, sizeof(int), com);
    long long ans1 = 0, ans2 = 0;
    for(int i = 0; i < n; i++) {
        if(i & 1) ans2 += num[i];
        else ans1 += num[i];
    }
    free(num);
    printf("%lld %lld", ans1, ans2);
}

时间复杂度：O(nlog(n))，主要来自快排
空间复杂度：O(n)，一个num数组

B小柒的交替子数组

链接：https://ac.nowcoder.com/acm/contest/111921/B

解法一：

由于奇偶交替数组可以分为两种

• 开头为奇数
• 开头为偶数

很容易想到动态规划，从下标 0 到下标 i 所要操作的次数。可以用两个 dp 数组来完成，数组 dp0 表示开头为偶数情况，数组 dp1 表示开头为奇数情况。

• dp0:开头为偶数，即偶数下标为偶数，奇数下标为奇数
• dp1:开头为奇数，即偶数下标为奇数，奇数下标为偶数

在此之前先对原数组进行预处理：即奇数化一 偶数化零

    int* num = malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++) {
        int temp;
        scanf("%d", &temp);
        num[i] = (temp & 1);
    }

状态转移方程也很好写：

    dp0[0] = (num[0] != 0);    // 初始化dp0
    dp1[0] = (num[0] != 1);    // 初始化dp1
    for (int i = 1; i < n; i++) {
       dp0[i] = dp0[i-1] + (num[i] != (i&1 ? 1 : 0)); 
      // 当前状态 = 前一个状态 + 当前数字在 dp0 情况下是否需要操作（是即为1，否即为0）  
       dp1[i] = dp1[i-1] + (num[i] != (i&1 ? 0 : 1));
      // 当前状态 = 前一个状态 + 当前数字在 dp1 情况下是否需要操作（是即为1，否即为0）
    }  
// 其实就是看当前数字（0 或 1）与理想状态下数字（0 或 1）是否相同，相同则条件表达式为错，返回0；不同则条件表达式正确，返回1；

要知道我们现在推出的dp0 dp1数组的含义是从下标零到下标i所要操作的次数，但题目是要求在长度为n的数组中截取连续长度为m的数组所需最少操作次数。没错，就是前缀和

    for (int i = m-1; i < n; i++) {
        int start = i - m + 1;
        int cost0 = dp0[i] - (start > 0 ? dp0[start-1] : 0);
        int cost1 = dp1[i] - (start > 0 ? dp1[start-1] : 0);
        ans = fmin(ans, fmin(cost0, cost1));  // 每次取最小值
    }

Code

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h> 

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    int* num = malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++) {
        int temp;
        scanf("%d", &temp);
        num[i] = (temp & 1);
    }

    int ans = n;
    int* dp0 = malloc(sizeof(int) * n); 
    int* dp1 = malloc(sizeof(int) * n); 

    dp0[0] = (num[0] != 0); 
    dp1[0] = (num[0] != 1); 
    for (int i = 1; i < n; i++) {
        dp0[i] = dp0[i-1] + (num[i] != (i&1 ? 1 : 0)); 
        dp1[i] = dp1[i-1] + (num[i] != (i&1 ? 0 : 1)); 
    }

    for (int i = m-1; i < n; i++) {
        int start = i - m + 1;
        int cost0 = dp0[i] - (start > 0 ? dp0[start-1] : 0);
        int cost1 = dp1[i] - (start > 0 ? dp1[start-1] : 0);
        ans = fmin(ans, fmin(cost0, cost1));
    }

    free(num);
    free(dp0);
    free(dp1);
    printf("%d\n", ans);
    return 0;
}  

时间复杂度：O(n)
空间复杂度：O(n)

解法二：

动态规划 + 前缀和 固然很优秀，但为什么不直接一步到位滑动窗口解决呢

Code

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h> 

int main() {
    int N, M;
    scanf("%d %d", &N, &M);
    int *v = (int *)malloc(N * sizeof(int));
    for(int i = 0; i < N; i++) {
        int temp;
        scanf("%d", &temp);
        v[i] = temp & 1;
    }
  // 同样的预处理
  
    int ans = N, cur = 0;
  // 这里直接以开头为偶数为理想状态情况（其实随便取都一样）
    for(int i = 0; i < N; i++) {
        // 计算当前位置元素奇偶性与理想奇偶性（基于位置 i）的差异
        cur += v[i] ^ (i & 1);
        // 当窗口长度超过 M 时，移除窗口左端元素的影响
        if (i >= M) {
            cur -= v[i - M] ^ ((i - M) & 1);
        }
        // 当窗口长度达到 M - 1 及以上时，计算并更新最小操作次数
        if (i >= M - 1) {
            // 取当前差异值和其补集（M - cur）中的较小值，再更新全局最小值
            ans = fmin(ans, fmin(cur, M - cur));
        }
    }
    printf("%d\n", ans);
    free(v);
    return 0;
}

时间复杂度：O(n)
空间复杂度：O(n)

C小柒的幸运数

链接：https://ac.nowcoder.com/acm/contest/111921/C

一开始想法是二维动态规划，嗯，好吧，还是官解厉害，采用滑动窗口结合字符频次统计的方法，动态维护窗口内的逆序对数量。

核心思想

• 滑动窗口：用双指针left和right表示窗口的左右边界，逐步扩展右边界，并在逆序对数量超过 x 时收缩左边界。
• 逆序对计算：利用数组phala统计窗口中各字符的出现次数
  • 新增字符时，累加比它大的字符数量。
  • 移除字符时，减少比它小的字符数量。

Code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

 int main() {
     char s[200005];
     long long x;
     scanf("%s %lld", s, &x);
     int len = strlen(s);
     long long phala[26];
     int left = 0, right = 0;
     long long val = 0, now = 0;
     
     for(;right < len; right++) {
         int current_char = s[right] - 'a';
         for(int i = current_char + 1; i < 26; i++) {
             now += phala[i];
         }
         phala[current_char]++;
        // 时刻更新 val
         if(llabs(val - x) > llabs(now - x)) {
             val = now;
         }
         
         if(val == x) break;  // 提前结束，小优化
       
       // 这里应是 while, 而非 if, 维持边界要一步到位！
         while(left <= right && now > x) {
             int left_char = s[left] - 'a';
             for(int i = 0; i < left_char; i++) {
                 now -= phala[i];
             }
             phala[left_char]--;
             left++;
            // 时刻更新 val
             if(llabs(val - x) > llabs(now - x)) {
                 val = now;
             }
         }
     }
     printf("%lld\n", llabs(val - x));  // 注意最后输出的是差的绝对值
     return 0;
 }

时间复杂度：O(26n), 每个字符最多被加入和移除窗口各一次，每次操作需遍历 26 个字母。
空间复杂度：O(26), 即为 phala 数组