AcWing 第140场周赛

发表于 更新于 分类于 阅读次数： 本文字数： 509 阅读时长 ≈ 2 分钟
Life does not have to be perfect to be wonderful.

A. 判断序列

思路：

  • 直接从前往后判断相邻位置的差值是不是1即可

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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];
    }

    for (int i = 0; i + 1 < n; i++) {
        if (a[i + 1] - a[i] != 1) {
            std::cout << "NO\n";
            return 0;
        }
    }
    std::cout << "YES\n";

    return 0;
}

B. 修改数列

思路：

  • 枚举向量-1,0,1然后运用中学所学的等差数列的知识，求出在当前向量下的公差和首项，然后枚举比较是否会出现差值大于1的情况，如果出现了那么在当前的初始向量的情况下就一定不可能是等差数列

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

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
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];
    }

    auto solve = [&](int i, int j) {
        int x = a[0] + i, d = a[1] + j - x;
        int res = abs(i) + abs(j);

        for (int i = 2; i < n; i++) {
            int t = x + i * d;
            int dif = abs(t - a[i]);
            if (dif > 1) return int(2E9);
            res += dif;
        }
        return res;
    };

    int ans = 2E9;
    for (int i = -1; i <= 1; i++) {
        for (int j = -1; j <= 1; j++) {
            ans = std::min(solve(i, j), ans);
        }
    }
    std::cout << (ans == 2E9 ? -1 : ans) << "\n";

    return 0;
}

C. 安排时间

思路：

  • 首先，将序列按每一个顾客的到店时间升序排序，然后从到店的那一刻开始准备，如果出现准备小于需要准备的最小时间 \(c_i\) ，那么直接输出 \(-1\)​ 即可

时间复杂度：\(O(mlogm+m)\)

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
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, m;
    std::cin >> n >> m;

    std::vector<int> ans(n + 1);
    std::vector<std::array<int, 4>> a(m);
    for (int i = 0; i < m; i++) {
        std::cin >> a[i][0] >> a[i][1] >> a[i][2];
        a[i][3] = i + 1;
        ans[a[i][1]] = m + 1;
    }

    std::sort(a.begin(), a.end(), [&](auto i, auto j) {
        return i[1] < j[1];
    });

    for (int i = 0; i < m; i++) {
        int cnt = 0;
        for (int j = a[i][0]; j < a[i][1] && cnt < a[i][2]; j++) {
            if (ans[j] == 0) {
                ans[j] = a[i][3];
                cnt++;
            }
        }
        if (cnt < a[i][2]) {
            std::cout << "-1\n";
            return 0;
        }
    }
    for (int i = 1; i <= n; i++) {
        std::cout << ans[i] << " \n"[i == n];
    }

    return 0;
}