题面解释:

在这道题中，给定若干磁盘，每个磁盘具有一定的容量，数据需要按照三种可能的写入策略（轮循写入、优先剩余空间写入、按比例轮循写入）写入到磁盘中。题目要求根据输入的写入策略切换频率、写入数据量和写入比例，判断有多少种写入策略可以使得所有磁盘的空间占用率保持均衡。如果有多种策略满足条件，则输出这些策略的数量；如果没有满足条件的策略，则返回0。

思路

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

问题分析

题目要求我们模拟写入数据到多块硬盘的过程，并且需要保证写入后的硬盘占用率尽量保持均衡。为了实现这一点，我们可以通过深度优先搜索（DFS）遍历不同的写入策略组合，找到所有可能使占用率均衡的方案。题目中给出的三种写入策略分别为：

1. 轮循写入：依次将数据写入不同的磁盘，直到数据写完或者空间不足。
2. 优先写入剩余空间大的磁盘：每次写入时选择剩余空间最大的磁盘进行写入。
3. 按比例写入：根据磁盘的容量比例按比例分配写入数据。

我们的目标是通过这些策略的组合来写入指定的数据量，最终使各个磁盘的空间占用率保持均衡。我们通过深度优先搜索的方式，遍历所有可能的写入策略组合，判断每种组合是否可以使占用率保持均衡。

解题思路

1. 深度优先搜索（DFS）：我们使用DFS遍历不同的写入策略组合，每次可以选择三种写入策略中的一种。每当数据写入完成后，判断当前各个磁盘的占用率是否均衡。如果均衡则计数。
2. 写入策略的模拟：对于每种写入策略，我们分别实现了轮循写入、优先写入和按比例写入的模拟。每种策略都按照固定规则写入数据，更新磁盘的剩余空间。
3. 占用率的检查：在每次DFS的终点，我们检查所有磁盘的占用率是否相等。占用率定义为磁盘写入的数据量除以磁盘的总容量。如果所有磁盘的占用率都相等，则认为该写入策略组合是有效的。
4. 分数化简：为了方便比较占用率是否相等，我们将占用率分数化简为最简分数进行比较。

代码如下

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) { // 处理特殊情况：当容量为0时
            if (a != 0) return false; // 如果有数据写入却容量为0，返回不均衡
            occ_rate[i] = {0, 1}; // 定义占用率为 0
        } 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) { // 每次写入 4KB 数据
        if (res_size[i] >= 4) { // 如果当前磁盘有足够空间写入 4KB
            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) { // 如果当前磁盘有足够空间写入 4KB
            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) {
        if (res_size[i] >= 4 * rate[i]) { // 按比例写入
            res_size[i] -= 4 * rate[i];
            cnt += rate[i];
        } else { // 如果不够按比例写入
            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; // 如果均衡，方案数加 1
        }
        return;
    }

    // 尝试轮循写入策略
    int cnt_cir = 0;
    int write_times_cir = min(rest_write_time, n); // 最多写入 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); // 最多写入 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); // 最多写入 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); // 关闭同步，提高IO速度
    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); // 开始DFS搜索
    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]);
    }
}

小明的提醒:

本题数据范围有误导性！本题在笔试过程中使用dfs回溯法就能过所有数据，所以官方后台数据应该都是在很小的范围内。

题目内容

存储软件负责编程按照某写入策略，每次可向单块磁盘写入$4KB$数据，每写入$n$次可随机分配一次写入策略，存储软件的写入策略分为$3$种：

策略一： 轮循写入：比如存在$3$块硬盘$0$、$1$、$2$，

当$n=2$，采用该策略写入数据时，写入顺序为$0$->$1$；

当$n=5$，采用该策略写入数据时，写入顺序为$0$->$1$->$2$->$0$->$1$。

策略二： 优先写入剩余空间高的磁盘（剩余空间相同时，先写入序号小的硬盘），比如存在$3$块硬盘$0$、$1$、$2$，空间容量分别为$12KB$、$16KB$、$24KB$，

当$n=2$，采用该策略写入数据时，写入顺序为$2$->$2$，

当$n=5$，采用该策略写入数据时，写入顺序为$2$->$2$->$1$->$2$->$0$。

策略三： 按比例轮循写入：比如存在$3$块硬盘$0$、$1$、$2$，

当$n=3$，采用该策略写入数据时，数据写入顺序为$0$->$1$->$1$；

当$n=6$，采用该策略写入数据时，数据写入顺序为$0$->$1$->$1$->$2$->$2$->$2$。

切换写入策略时，可切换不同的策略也可以和上次策略保持一致，切换策略后不继承上次写入策略的执行结果，如：$3$块硬盘$0$、$1$、$2$，写入比例为$1:1:2$，待写入的数据量有$24KB$，

当$n=2$，一直通过策略$1$写入数据，写入顺序为（策略$1$）$0$->$1$->（策略$1$）$0$->$1$->（策略$1$）$0$->$1$；

当$n=2$，一直通过策略$3$写入数据，写入顺序为（策略$3$）$0$->$1$->（策略$3$）$0$->$1$->（策略$3$）$0$->$1$；

当$n=5$，一直通过策略$1$写入数据，写入顺序为（策略$1$）$0$->$1$->$2$->$0$->$1$->（策略$1$）$0$；

当$n=5$，一直通过策略$3$写入数据，写入顺序为（策略$3$）$0$->$1$->$2$->$2$->$0$->（策略$3$）$0$。

现在有一批数据要写入初始状态为空的硬盘，存在几种写入策略分配使最后硬盘空间的占用率（硬盘空间的占用率=硬盘写入的数据量/硬盘的总容量）保持均衡。

注：

1.如果不存在合适的写入策略分配使最后硬盘空间的占用率保持均衡，则返回$0$；

2.如果存在合适的写入策略，最终的磁盘空间占用率一定是整除的结果，精度$>0.000001$。

3.不管是否写入成功，都算一次。例如:

策略是轮循写入，n = 3 , 磁盘是0 , 1 , 2 . 但是1,2都满了。程序还是0,1,2的写，失败了也算数。而不是0.跳过1,2，写0，再跳过1,2，再写0!

输入描述

磁盘的个数$[1,200]$

每个磁盘的容量（单位$KB$，空间是$4$的倍数）$[1,10000]$

磁盘的写入比例$[1,1000]$

待写入的总数据量（单位$KB$，总数据量是$4$的倍数）$[1,1000]$

每$n$次切换一次写入策略$[1,1000]$

输出描述

存在几种写入策略分配

样例1

输入

3
64 64 64
1 1 1
12
3

输出

3

说明

总共有3块硬盘，每块硬盘有64KB容量，三块硬盘的

1:1，待写入12KB数据，每3次切换一次写入策略，共

略分配使最后的硬盘空间的占用率保持平衡。

方式1：策略1

方式2：策略2

方式3：策略3

采用3种方式均能保持写入后3块硬盘的空间占用率保

4/64=0.0625

样例2

输入

3
128 64 32
4 2 1
56
7

输出

1

说明