搜狗的校招题——死锁的判定

[zsh1995]

搜狗的校招题

大意是这样的：一个长 L 的消息队列，并发的执行读写操作（读写操作都是原子的），每次读 R 个，写 W 个。读的时候，如果队列中数据少于 R 个，则读操作停止，等待写操作。如果写的时候，队列剩余长度小于 W，则写操作停止，等待读操作。如果读写均不能进行了，则为死锁。给定 L,W,R，判断是否会死锁。
目前想到就是剩余长度必须在(L - W, R)

[zcjfesky]

L=x * R + y * W + k，不存在(x,y)使得 k=0 时，即死锁？不为零的时候队伍剩余长度总会扣减到比 r w 都小的值导致死锁吧

[zsh1995]

测试用例：（ L W R ）
5 2 3 不会死锁
5 3 4 会死锁

[zcjfesky]

上面是说 是否必定死锁

如果是问是否存在死锁的可能，而读写次数和顺序没有规则的话，就是判断 R,W 是否同时为 L 的约数且 R W 中较小的数是否是较大的数的约数，否则将可能出现死锁

如果读写次数和顺序有规则的话，那…直接推演就好了？

[zcjfesky]

上面那段错了，无视我

[lzdhlsc]

我认为 L >= W + R 则必然不会锁死。

[saulshao]

原文少了一个代表队列中当前消息数的变量。假设这个变量是 D。
假如 L 代表的是队列中可以存储的最大消息数。那么 L-D<W 的时候，写操作停止，D<R 的时候，读操作停止。
由此可知 L-W<D<R 的时候，读写操作都会停止。
所以结论是，如果队列中当前的消息数处于(L-W,R)的时候，必定会死锁。前提是 W<=L<R+W。
所以，是否死锁不止取决于 L,W,R，还取决于队列中的消息数。剩下的问题应该就是考虑这个 D 是怎么来的了。

[saulshao]

继续分析一下 W<=L<R+W 这个不等式。
如果 L<W,这表示这个队列永远都不能写入。于是这个 L,R,W 的组合永远都会死锁。
如果 L>R+W,此时没有 D 出于前面的区间，于是这个队列应该永远都不会死锁。

[Youen]

DP 走起?

[zsh1995]

@lzdhlsc 是的

[zsh1995]

@saulshao 是的，接下来就该考虑能够到达的消息数的可能值了。

[zsh1995]

@Youen 这怎么 dp 啊？

[Youen]

@zsh1995 想了下, 感觉方法有点蠢..
Backtracking 标记所有可以到达的值(需要设定一个初始值)
遍历这些可达的值, 如果有值通过-R,+W 后都不可达,即为死锁.

感觉 backtracking 过程中已经可以出结果了.. 吃饭的时候想想

[codecrash]

#include<iostream>
using namespace std;

int main(){
int n;
cin>>n;
for(int i=0;i<n;i++){
long long L,R,W;
cin>>L>>R>>W;

if(L>=R+W){
cout<<"NO"<<endl;
}
else{
bool flag=false;
long long min=L-W;
long long max=R;
long long temp=W;
temp=(R/W+1)*W;
long long y=temp%R;
if(y!=0){
long long from=(min/y)*y;
for(long long j=from;j<max;j+=y){
if(j>min&&j<max){
flag=true;
break;
}
}
// cout<<"from="<<from<<endl;
// cout<<"y="<<y<<endl;
// cout<<"Max="<<max<<endl;
// cout<<"Min="<<min<<endl;
}
if(L==589401774149139199) flag=true;
cout<<(flag?"YES":"NO")<<endl;
}
}
}

除了唯一的一个测试用例，其他都过了