题目链接

算法竞赛进阶指南-19.七夕祭

Method : 排序

先看一下本题的前置题目，均分纸牌 和 环形均分纸牌

b[N] = a[N] - avg;

s[i] = s[i - 1] + b[i]; // 求b[i]的前缀和，然后对前缀和求abs之和算cost

#include <iostream>

using namespace std;

const int N = 100 + 7;

int n;
int a[N];
int s[N];

int main() {
    // 可以得到target平均数，难办的是移动次数
    cin >> n;
    int sum = 0;
    for (int i = 1; i <= n; i ++) {
        scanf("%d", &a[i]);
        sum += a[i];
    }
    
    int avg = sum / n;
    for (int i = 1; i <= n; i ++) {
        a[i] -= avg;
    }
    
    int res = 0;
    int cost = 0;
    for (int i = 1; i <= n; i ++) {
        s[i] = s[i - 1] + a[i];
        if (s[i] != 0) res ++;
        // cost += abs(s[i]);   // 计算每次只能移动一个的移动次数
    }
    
    cout << res << endl;
    
    return 0;
}

基础位运算，本题是快速幂的模板题。

注意两点:

1. 有取模运算时不要用自乘*=， 否则会影响计算顺序
2. return 时也要取模， 防止极端例子:n = 0且p = 1

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

LL a, b, p;

LL fast_pow(LL x, LL n) {
    LL res = 1LL;
    while (n) {
        if (n & 1) {
            res = res * x % p;
        }
        x = x * x % p;
        n = n >> 1;
    }
    return res % p;
}

int main() {
    cin >> a >> b >> p;
    cout << fast_pow(a, b) << endl;
    return 0;
}

复杂度分析

• 时间复杂度${O(log_2n)}$， 其中$log_2n$为对n进行二进制拆分的时间复杂度。

• 空间复杂度${O(1)}$。