AcWing 第141场周赛

发表于 更新于 分类于 阅读次数： 本文字数： 377 阅读时长 ≈ 1 分钟
Life is too short for us to wake up in the morning with regrets.

A. 客人数量

思路：

  • 求总和即可

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    std::cin >> n;

    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }

    std::cout << std::accumulate(a.begin(), a.end(), 0) << "\n";
    
    return 0;
}

B. 指针运动

思路：

  • 模拟，从序列中出现第一个 \(0\) 的位置开始继续走，出现 \(a[t \% n] - t <= 0\)​ 的位置就是答案所在位置

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    std::cin >> n;

    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }

    int t = *min_element(a.begin(), a.end());

    while (a[t % n] - t > 0) {
        t++;
    }
    std::cout << t % n + 1 << "\n";

    return 0;
}

C. 随机排列

思路：

  • 根据逆序对的数量与数组长度判断需要的次数的奇偶性即可

时间复杂度：\(O(nlogn)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
constexpr int N = 1000010;
int tmp[N];//中转数组
int a[N];//原数组
int n;//数据大小

int merge_sort(int a[], int l, int r) {
    if (l >= r) return 0;

    int mid = l + r >> 1;

    int res = merge_sort(a, l, mid) + merge_sort(a, mid + 1, r);

    int k = 0, i = l, j = mid + 1;

    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) tmp[k++] = a[i++];
        else {
            res += mid - i + 1;
            tmp[k++] = a[j++];
        }
    }
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= r) tmp[k++] = a[j++];

    for (int i = l, j = 0; i <= r; i++, j++) a[i] = tmp[j];

    return res;
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
     std::cin >> n;

     for (int i = 1; i <= n; i++) {
         std::cin >> a[i];
     }
    
     int t = merge_sort(a, 1, n);

     int ans = -1;
     if (n % 2 == 0) {
         if (t & 1) {
             ans = 2;
         } else {
             ans = 1;
         }
     } else {
         if (t % 2 == 0) {
             ans = 2;
         } else {
             ans = 1;
         }
     }
     std::cout << ans << "\n";

    return 0;
}