题面解释

给定若干块磁盘，每块磁盘有不同的容量，按照某种写入比例，向这些磁盘写入一定量的数据。写入过程可以根据不同的策略，每隔几次切换一次策略。目标是找到使得所有磁盘的空间占用率保持均衡的写入策略组合数量。若不存在这样的组合，则返回0。

输入包括：磁盘数量、每块磁盘的容量、写入比例、待写入的数据量以及每几次切换一次写入策略。输出是存在多少种写入策略组合能够使磁盘的空间占用率保持均衡。

思路

dfs+模拟，对于目前的这次选择什么策略，考虑dfs去遍历每一种策略，第一种策略也就是按轮循写入(1 2 3 1 2 3....),第二组是每一次都选择目前剩余容量高的，第三种则是按比例，看最后看硬盘空间的占用率是不是保持均衡即可

题目理解

给定若干块磁盘，每块磁盘有不同的容量，并按照一定的写入比例，向这些磁盘写入一定量的数据。每隔几次写入后可以切换写入策略，我们需要找到使得所有磁盘的空间占用率保持均衡的写入策略组合数量。题目要求通过三种策略进行写入：

1. 轮循写入策略：按照轮流顺序依次写入各个磁盘（比如，磁盘 0 -> 1 -> 2 -> 0 -> 1）。
2. 优先剩余空间多的磁盘写入策略：每次优先选择剩余空间最多的磁盘进行写入，如果容量相同，则选择序号较小的磁盘。
3. 按比例写入策略：根据给定的比例，将数据按比例写入各个磁盘。

思路

1. 模拟三种写入策略：

   • 轮循写入：按照顺序写入，依次从第一个磁盘写到最后一个磁盘，再循环写回第一个磁盘。
   • 优先剩余空间多的磁盘：每次选择剩余空间最大的磁盘进行写入。
   • 按比例写入：按照给定的比例，向各个磁盘分配写入的数据。

2. DFS（深度优先搜索）：

   • 使用DFS去模拟每一次的写入选择，每次根据当前的剩余写入次数，遍历三种写入策略。
   • 在搜索结束时，检查所有磁盘的占用率是否均衡。如果均衡，计数加1。

3. 判断磁盘空间占用率是否均衡：

   • 通过计算每个磁盘已写入的数据量与其总容量的比例，并用最简分数形式表示。如果所有磁盘的占用率相同，则认为占用率均衡。

关键函数说明

1. get_simple(int a, int b)：

   • 计算两个整数的最简分数形式。用于判断磁盘空间占用率是否相等。

2. check(const vector<int>& final_size, const vector<int>& original_size, int m)：

   • 检查所有磁盘的最终占用率是否相等。如果相等，则返回true。

3. circle_write、priority_write、rate_write：

   • 这三个函数分别实现了三种写入策略的模拟，每个函数都会根据不同的策略进行写入并返回更新后的磁盘剩余空间。

4. dfs：

   • 通过DFS遍历每种写入策略，在每次选择不同的策略后递归处理剩余的写入操作，最终判断是否能达到占用率均衡的情况。

代码如下

Python

import math
m = int(input())
size = list(map(int, input().split()))
rate = list(map(int, input().split()))
tot_wirte_size = int(input())
n = int(input())
ans = 0
# 循环写入
def circle_write (size , n , m):
    res_size = size.copy()
    i = 0
    cnt = 0
    while n > 0:
        if res_size[i] >= 4:
            res_size[i] -= 4
            cnt += 1 # 只有实际写入了才算一次
        n -= 1
        i = (i + 1) % m
    return res_size , cnt
# 优先写入
def priority_write (size , n):
    res_size = size.copy()
    cnt = 0
    while n > 0:
        # 优先写入最大的硬盘
        i = res_size.index(max(res_size))
        if res_size[i] >= 4:
            res_size[i] -= 4
            cnt += 1
        n -= 1
    return res_size , cnt
# 按比例写入
def rate_write (size , n , m , rate):
    res_size = size.copy()
    cnt = 0
    i = 0
    while n > 0:
        # 够写rate[i]次,直接写入
        if res_size[i] >= 4 * rate[i]:
            res_size[i] -= 4 * rate[i]
            cnt += rate[i]
        else:
            # 不够写rate[i]次,那么就写入到最后一次
            res_size[i] %= 4
            cnt += res_size[i] // 4
        n -= rate[i]
        i = (i + 1) % m
    return res_size , cnt

# 使用math.gcd得到分子/分母的最简形式
def get_simple (a , b):
    return [a // math.gcd(a , b) , b // math.gcd(a , b)]

# 检查磁盘占用率是否全部相等
def check (final_size , n , m):
    global size
    # 计算磁盘占用率
    occ_rate = []
    for i in range(m):
        # 计算分子/分母的最简形式,这样就不会有浮点数误差了
        occ_rate.append(get_simple(size[i] - final_size[i] , size[i]))
    # 检查是否相等
    for i in range(1 , m):
        if occ_rate[i] != occ_rate[0]:
            return False
    return True 

way = []
def dfs (size , rest_wirte_time):
    global n , rate , m , ans
    if rest_wirte_time == 0:
        if check(size , n , m):
            ans += 1
            #print(way , "gg")
        return
    # 分别计算三种方式的结果

    size_cir , cnt = circle_write(size , min(rest_wirte_time , n) , m)
    # 如果前后硬盘的状态不相等,代表这个策略是有效的,那么就递归继续执行了
    if size != size_cir:
        dfs(size_cir , rest_wirte_time - cnt)

    size_pri , cnt = priority_write(size , min(rest_wirte_time , n))
    if size != size_pri:
        dfs(size_pri , rest_wirte_time - cnt)
    
    size_rat , cnt = rate_write(size , min(rest_wirte_time , n) , m , rate) 
    if size != size_rat:
        dfs(size_rat , rest_wirte_time - cnt)

dfs(size , tot_wirte_size // 4)
print(ans)

cpp

#include <bits/stdc++.h>
using namespace std;

// 使用 std::gcd 得到分子/分母的最简形式
pair<int, int> get_simple(int a, int b) {
    if (b == 0) {
        return {0, 1}; // 定义 0/1 当分母为 0
    }
    int g = __gcd(a, b);
    return {a / g, b / g};
}

// 检查磁盘占用率是否全部相等
bool check(const vector<int>& final_size, const vector<int>& original_size, int m) {
    vector<pair<int, int>> occ_rate(m);
    for (int i = 0; i < m; i++) {
        int a = original_size[i] - final_size[i];
        int b = original_size[i];
        if (b == 0) {
            if (a != 0)
                return false;
            else {
                occ_rate[i] = {0, 1};
            }
        }
        else {
            occ_rate[i] = get_simple(a, b);
        }
    }
    for (int i = 1; i < m; i++) {
        if (occ_rate[i] != occ_rate[0]) {
            return false;
        }
    }
    return true;
}

// 循环写入
vector<int> circle_write(const vector<int>& size, int n, int m, int& cnt) {
    vector<int> res_size = size;
    int i = 0;
    cnt = 0; // 初始化写入计数
    while (n > 0) {
        if (res_size[i] >= 4) {
            res_size[i] -= 4;
            cnt += 1;
        }
        n -= 1;
        i = (i + 1) % m;
    }
    return res_size;
}

// 优先写入
vector<int> priority_write(const vector<int>& size, int n, int& cnt) {
    vector<int> res_size = size;
    cnt = 0; // 初始化写入计数
    while (n > 0) {
        // 找到第一个最大元素的索引（从左到右）
        int max_val = *max_element(res_size.begin(), res_size.end());
        auto max_it = find(res_size.begin(), res_size.end(), max_val);
        int i = distance(res_size.begin(), max_it);
        if (res_size[i] >= 4) {
            res_size[i] -= 4;
            cnt += 1;
        }
        n -= 1;
    }
    return res_size;
}

// 按比例写入
vector<int> rate_write(const vector<int>& size, int n, int m, const vector<int>& rate, int& cnt) {
    vector<int> res_size = size;
    cnt = 0; // 初始化写入计数
    int i = 0;
    while (n > 0) {
        // 够写 rate[i] 次, 直接写入
        if (res_size[i] >= 4 * rate[i]) {
            res_size[i] -= 4 * rate[i];
            cnt += rate[i];
        }
        else {
            // 不够写 rate[i] 次, 那么就写入到最后一次
            res_size[i] %= 4;
            cnt += res_size[i] / 4;
        }
        n -= rate[i];
        i = (i + 1) % m;
    }
    return res_size;
}

// 深度优先搜索
void dfs(vector<int>& size, int rest_write_time, int& ans, int n, const vector<int>& rate, int m, const vector<int>& original_size) {
    if (rest_write_time == 0) {
        if (check(size, original_size, m)) {
            ans += 1;
        }
        return;
    }

    // 循环写入
    int cnt_cir = 0;
    int write_times_cir = min(rest_write_time, n);
    vector<int> size_cir = circle_write(size, write_times_cir, m, cnt_cir);
    if (size != size_cir) {
        dfs(size_cir, rest_write_time - cnt_cir, ans, n, rate, m, original_size);
    }

    // 优先写入
    int cnt_pri = 0;
    int write_times_pri = min(rest_write_time, n);
    vector<int> size_pri = priority_write(size, write_times_pri, cnt_pri);
    if (size != size_pri) {
        dfs(size_pri, rest_write_time - cnt_pri, ans, n, rate, m, original_size);
    }

    // 按比例写入
    int cnt_rat = 0;
    int write_times_rat = min(rest_write_time, n);
    vector<int> size_rat = rate_write(size, write_times_rat, m, rate, cnt_rat);
    if (size != size_rat) {
        dfs(size_rat, rest_write_time - cnt_rat, ans, n, rate, m, original_size);
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int m;
    cin >> m;
    vector<int> size(m);
    for(int i=0; i<m; i++) cin >> size[i];
    
    vector<int> rate(m);
    for(int i=0; i<m; i++) cin >> rate[i];
    
    int tot_write_size;
    cin >> tot_write_size;
    
    int n;
    cin >> n;
    
    int ans = 0;
    vector<int> original_size = size; // 保存原始大小
    int rest_write_time = tot_write_size / 4;
    
    dfs(size, rest_write_time, ans, n, rate, m, original_size);
    cout << ans << "\n";
    
    return 0;
}

Java

import java.io.*;
import java.util.*;

public class Main {
    
    // 辅助类，用于保存写入操作的结果
    static class Result {
        List<Integer> size;
        int cnt;
        Result(List<Integer> size, int cnt){
            this.size = size;
            this.cnt = cnt;
        }
    }
    
    // 辅助类，用于表示简化后的分数
    static class SimpleFraction {
        int numerator; // 分子
        int denominator; // 分母
        SimpleFraction(int numerator, int denominator){
            this.numerator = numerator;
            this.denominator = denominator;
        }
        
        @Override
        public boolean equals(Object o){
            if(this == o) return true;
            if(o == null || getClass() != o.getClass()) return false;
            SimpleFraction that = (SimpleFraction) o;
            return numerator == that.numerator && denominator == that.denominator;
        }
        
        @Override
        public int hashCode(){
            return Objects.hash(numerator, denominator);
        }
    }
    
    // 获取 a/b 的最简形式
    static SimpleFraction get_simple(int a, int b){
        if(b == 0){
            if(a == 0){
                return new SimpleFraction(0, 1);
            }
            else{
                // 未定义的占用率；在 check 函数中处理这种情况
                return new SimpleFraction(0, 1);
            }
        }
        int g = gcd(a, b);
        return new SimpleFraction(a / g, b / g);
    }
    
    // 检查所有磁盘占用率是否相等
    static boolean check(List<Integer> final_size, List<Integer> original_size, int m){
        List<SimpleFraction> occ_rate = new ArrayList<>();
        for(int i = 0; i < m; i++){
            int a = original_size.get(i) - final_size.get(i);
            int b = original_size.get(i);
            if(b == 0){
                if(a != 0){
                    return false;
                }
                else{
                    occ_rate.add(new SimpleFraction(0, 1));
                }
            }
            else{
                occ_rate.add(get_simple(a, b));
            }
        }
        // 与第一个占用率进行比较
        for(int i = 1; i < m; i++){
            if(!occ_rate.get(i).equals(occ_rate.get(0))){
                return false;
            }
        }
        return true;
    }
    
    // 循环写入策略
    static Result circle_write(List<Integer> size, int n, int m){
        List<Integer> res_size = new ArrayList<>(size);
        int i = 0;
        int cnt = 0; // 初始化写入计数
        while(n > 0){
            if(res_size.get(i) >= 4){
                res_size.set(i, res_size.get(i) - 4);
                cnt += 1;
            }
            n -= 1;
            i = (i + 1) % m;
        }
        return new Result(res_size, cnt);
    }
    
    // 优先写入策略
    static Result priority_write(List<Integer> size, int n){
        List<Integer> res_size = new ArrayList<>(size);
        int cnt = 0; // 初始化写入计数
        while(n > 0){
            // 找到最大元素的第一个出现位置
            int max_val = Collections.max(res_size);
            int i = res_size.indexOf(max_val);
            if(res_size.get(i) >= 4){
                res_size.set(i, res_size.get(i) - 4);
                cnt += 1;
            }
            n -= 1;
        }
        return new Result(res_size, cnt);
    }
    
    // 按比例写入策略
    static Result rate_write(List<Integer> size, int n, int m, List<Integer> rate){
        List<Integer> res_size = new ArrayList<>(size);
        int cnt = 0; // 初始化写入计数
        int i = 0;
        while(n > 0){
            // 够写 rate[i] 次，直接写入
            if(res_size.get(i) >= 4 * rate.get(i)){
                res_size.set(i, res_size.get(i) - 4 * rate.get(i));
                cnt += rate.get(i);
            }
            else{
                // 不够写 rate[i] 次，则写入到最后一次
                res_size.set(i, res_size.get(i) % 4);
                cnt += res_size.get(i) / 4;
            }
            n -= rate.get(i);
            i = (i + 1) % m;
        }
        return new Result(res_size, cnt);
    }
    
    // 深度优先搜索
    static void dfs(List<Integer> size, int rest_write_time, int[] ans, int n, List<Integer> rate, int m, List<Integer> original_size){
        if(rest_write_time == 0){
            if(check(size, original_size, m)){
                ans[0] += 1;
            }
            return;
        }
        
        // 循环写入
        int write_times_cir = Math.min(rest_write_time, n);
        Result size_cir_pair = circle_write(size, write_times_cir, m);
        List<Integer> size_cir = size_cir_pair.size;
        int cnt_cir = size_cir_pair.cnt;
        if(!size.equals(size_cir)){
            dfs(size_cir, rest_write_time - cnt_cir, ans, n, rate, m, original_size);
        }
        
        // 优先写入
        int write_times_pri = Math.min(rest_write_time, n);
        Result size_pri_pair = priority_write(size, write_times_pri);
        List<Integer> size_pri = size_pri_pair.size;
        int cnt_pri = size_pri_pair.cnt;
        if(!size.equals(size_pri)){
            dfs(size_pri, rest_write_time - cnt_pri, ans, n, rate, m, original_size);
        }
        
        // 按比例写入
        int write_times_rat = Math.min(rest_write_time, n);
        Result size_rat_pair = rate_write(size, write_times_rat, m, rate);
        List<Integer> size_rat = size_rat_pair.size;
        int cnt_rat = size_rat_pair.cnt;
        if(!size.equals(size_rat)){
            dfs(size_rat, rest_write_time - cnt_rat, ans, n, rate, m, original_size);
        }
    }
    
    // 计算最大公约数
    static int gcd(int a, int b){
        if(b == 0) return a;
        return gcd(b, a % b);
    }
    
    public static void main(String[] args){
        // 快速输入
        Scanner sc = new Scanner(System.in);
        
        int m = sc.nextInt();
        List<Integer> size = new ArrayList<>();
        for(int i = 0; i < m; i++) size.add(sc.nextInt());
        List<Integer> rate = new ArrayList<>();
        for(int i = 0; i < m; i++) rate.add(sc.nextInt());
        int tot_write_size = sc.nextInt();
        int n = sc.nextInt();
        
        int[] ans = new int[1];
        ans[0] = 0;
        List<Integer> original_size = new ArrayList<>(size);
        int rest_write_time = tot_write_size / 4;
        dfs(size, rest_write_time, ans, n, rate, m, original_size);
        System.out.println(ans[0]);
    }
}