首页 > 试题广场 >

死锁

[编程题]死锁
  • 热度指数：1262 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
试判断一个消息队列是否可能死锁。
消息队列的缓冲区长度为L单位，读操作为每次从缓冲区读取R单位，写操作为每次写入缓冲区W单位。
消息队列会持续进行读写操作。具体为写操作会在缓冲区还剩余大于等于W单位空间时保持进行，当缓冲区内空间小于W时，写操作停止，等待读操作进行；类似的，读操作会在缓冲区可读内容大于等于R时保持进行，当可读内容小于R时，读操作停止，等待写操作进行。读写都是原子操作。
若读写操作均无法进行，定义此时状态为死锁。
给定L,R,W，问消息队列是否可能进入死锁状态，若能，输出YES，否则输出NO

输入描述:
第1行输入N(N<=10)表示数据组数。
从第2行到第N+1行，每行三个整数L,R,W。


输出描述:
输出N行，每行输出'YES'或'NO'
示例1

输入

2
5 2 3
5 3 4

输出

NO
YES

备注:
50% L,R,W<=10^5
50% L,R,W<=10^18
算法知识视频讲解
添加回答
Python
白色纯度头像 白色纯度
我来抛砖引玉吧。
这道题目我们可以这么想，给定R和W时，能使消息不发生死锁的最小长度L应该是多少？
1. 理论上讲，死锁的情况不外乎 可读的数据量比R小，留下的缓冲区比W小，那么L为 R-1+W-1 时，是有可能发生死锁的。这似乎是个临界情况，因为只要 L大于 R-1+W-1 ，那么死锁基本不会出现。所以用 R-1+W-1 作为判定条件就可以了吗？ 显然不对，因为你根本无法保证 可读的数据量恰好就是 R-1。
2. 那么我们是否可以求出一个，在反复的读写操作中，数据量可以达到的最大长度length（长度在R以内）。在这个最大长度length的基础上，恰发生死锁，那么必有L=length+W-1.因此，恰好不发生死锁的长度就是length+W。
3. 最终问题指向了length的求解。请注意反复读写，反复的意思是什么？比如R=6，W=9，此时的length=3；R=3，W=4，此时的length=2；R=10，W=4，此时的length=8。这个过程中涉及到的思想就是辗转相除！辗转相除的目的是求最大公约数d，而本题目的不是求最大公约数d，而是求length，length=R-d。最大公约数d的本质就是，在R和W的操作中，可以抹除掉的数据量的最大数目d。那么R中留下来的一定就是length。
4. 所以L恰不发生死锁的长度就是length+W，即 R-d+W。其中的d用辗转相除法即可！
5. 留一个小问题：在（2）中为什么讨论的是R而不是W呢？欢迎大家留言讨论，过几天人多时，我再补充回复哈！ 
def is_ok(L,R,W):
    s=W+R
    d = W
    while True:
        if (d == 0):
            d = R
            break
        R = R % d
        if (R == 0):
            break
        d = d % R
    return "NO" if (L >= s-d) else "YES"
if __name__=='__main__':
    n = int(input().strip())
    for _ in range(n):
        l, r, w = list(map(int,input().split()))
        print(is_ok(l,r,w))
发表于 2019-08-20 10:48:23 回复(2)
C/C++
nbgao头像 nbgao 
#include <bits/stdc++.h>
using namespace std;

int main(){
    long N, L, R, W;
    scanf("%ld", &N);
    while(N--){
        scanf("%ld%ld%ld", &L, &R, &W);
        if(R+W-__gcd(R, W) > L)
            puts("YES");
        else
            puts("NO");
    }
    return 0;
}

发表于 2020-11-16 10:23:55 回复(0)
WindedMan头像 WindedMan
示例可以过  ，但是AC不了求大佬指点错在哪 
#include<bits/stdc++.h>
using namespace std;
int main(){
    int N;
    cin>>N;
    while(N--){
    long long L,R,W;
    cin>>L>>R>>W;
    
    long long Wlea=0,Rall=0,Rlea=0;
    while((L-Rlea)>=W){
    Wlea=(L-Rlea)%W;
    Rall=L-Wlea;
    if(Rall<R)Rlea=Rall;
    else Rlea=Rall%R;
    if(Rlea==0)break;
    }
    if(Rlea==0)cout<<"NO"<<endl;
    else cout<<"YES"<<endl;
    
    }
    return 0;
}

发表于 2020-03-03 21:51:36 回复(0)
izumi_ryouka头像 izumi_ryouka 
#include<iostream>
using namespace std;

bool isSisuo(long long L,long long R,long long W){
    long long x=0;
    for(long long j=0;j<1000;j++){
        if((L-x)>=W){
            x=x+W;
        }else{
            x=x-R;
            if(x<0){
                return true;
            }
        }
    }
    return false;
}

int main(){
    int num;
    cin>>num;
    long long L,R,W;
    for(int i=0;i<num;i++){
        cin>>L>>R>>W;
        if(isSisuo(L,R,W)){
            cout<<"YES"<<endl;
        }else{
            cout<<"NO"<<endl;
        }
    }
}
由于for循环次数不够，卡在了这组数据999999999999999888 633130390705049734 633130390705049735 YES 加了个过滤（手动滑稽）
编辑于 2019-12-05 16:36:59 回复(0)
提交观点

问题信息

C++工程师 iOS工程师 安卓工程师 小米集团 模拟 搜狗 算法工程师 队列 测试工程师 2019 Java工程师
来自：搜狗2019秋招客户端...
上传者：小小
难度：
4条回答 5091浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号