解题思路

这是一个内存读写死锁判断问题。关键点如下：

  1. 内存是环形的，总大小为
  2. 每次写入 字节，每次读取 字节
  3. 需要判断在什么情况下会发生死锁

判断逻辑：

  1. 如果 或 大于 ，必然死锁
  2. 如果 ，可以交替读写，不会死锁
  3. 如果 ，需要计算累积的可用空间是否足够读取
  4. 如果 ，需要计算写满后是否有足够空间读取

代码

#include <iostream>
using namespace std;

int main() {
    int L, R, W;
    cin >> L >> R >> W;
    
    if (R > L || W > L) {
        cout << "DEADLOCK" << endl;
        return 0;
    }
    
    if (R == W) {
        cout << "OK" << endl;
        return 0;
    }
    
    if (R < W) {
        int sum = 0;
        while (L - sum >= W) sum += W - R;
        cout << (sum < R ? "DEADLOCK" : "OK") << endl;
    } else {
        int sum = 0;
        while (sum <= L) sum += W;
        sum -= W;
        cout << (sum < R ? "DEADLOCK" : "OK") << endl;
    }
    
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int L = sc.nextInt(), R = sc.nextInt(), W = sc.nextInt();
        
        if (R > L || W > L) {
            System.out.println("DEADLOCK");
            return;
        }
        
        if (R == W) {
            System.out.println("OK");
            return;
        }
        
        if (R < W) {
            int sum = 0;
            while (L - sum >= W) sum += W - R;
            System.out.println(sum < R ? "DEADLOCK" : "OK");
        } else {
            int sum = 0;
            while (sum <= L) sum += W;
            sum -= W;
            System.out.println(sum < R ? "DEADLOCK" : "OK");
        }
    }
}

L, R, W = map(int, input().split())

if R > L or W > L:
    print("DEADLOCK")
elif R == W:
    print("OK")
elif R < W:
    sum = 0
    while L - sum >= W:
        sum += W - R
    print("DEADLOCK" if sum < R else "OK")
else:
    sum = 0
    while sum <= L:
        sum += W
    sum -= W
    print("DEADLOCK" if sum < R else "OK")

算法及复杂度

  • 算法：模拟
  • 时间复杂度： - 最坏情况下需要循环 次
  • 空间复杂度： - 只使用常数额外空间