这是一个创建于 2280 天前的主题，其中的信息可能已经有所发展或是发生改变。
搜狗的校招题
大意是这样的：一个长 L 的消息队列，并发的执行读写操作（读写操作都是原子的），每次读 R 个，写 W 个。读的时候，如果队列中数据少于 R 个，则读操作停止，等待写操作。如果写的时候，队列剩余长度小于 W，则写操作停止，等待读操作。如果读写均不能进行了，则为死锁。给定 L,W,R，判断是否会死锁。
目前想到就是剩余长度必须在(L - W, R)
 |
1
zcjfesky 2018-09-27 22:19:18 +08:00 via Android
L=x * R + y * W + k，不存在(x,y)使得 k=0 时，即死锁？不为零的时候队伍剩余长度总会扣减到比 r w 都小的值导致死锁吧
|
 |
2
zsh1995 OP 测试用例：（ L W R ）
5 2 3 不会死锁 5 3 4 会死锁 |
|
3
zcjfesky 2018-09-27 22:29:06 +08:00 via Android
上面是说 是否必定死锁
如果是问是否存在死锁的可能，而读写次数和顺序没有规则的话，就是判断 R,W 是否同时为 L 的约数且 R W 中较小的数是否是较大的数的约数，否则将可能出现死锁 如果读写次数和顺序有规则的话，那…直接推演就好了？ |
|
4
zcjfesky 2018-09-27 22:29:48 +08:00 via Android
上面那段错了，无视我
|
 |
5
lzdhlsc 2018-09-28 02:30:10 +08:00
我认为 L >= W + R 则必然不会锁死。
|
 |
6
saulshao 2018-09-28 09:23:24 +08:00
原文少了一个代表队列中当前消息数的变量。假设这个变量是 D。
假如 L 代表的是队列中可以存储的最大消息数。那么 L-D<W 的时候，写操作停止，D<R 的时候，读操作停止。 由此可知 L-W<D<R 的时候，读写操作都会停止。 所以结论是，如果队列中当前的消息数处于(L-W,R)的时候，必定会死锁。前提是 W<=L<R+W。 所以，是否死锁不止取决于 L,W,R，还取决于队列中的消息数。剩下的问题应该就是考虑这个 D 是怎么来的了。 |
|
7
saulshao 2018-09-28 09:40:02 +08:00
继续分析一下 W<=L<R+W 这个不等式。
如果 L<W,这表示这个队列永远都不能写入。于是这个 L,R,W 的组合永远都会死锁。 如果 L>R+W,此时没有 D 出于前面的区间，于是这个队列应该永远都不会死锁。 |
 |
8
Youen 2018-09-28 10:01:08 +08:00
DP 走起?
|
|
12
Youen 2018-09-28 13:08:34 +08:00
@zsh1995 想了下, 感觉方法有点蠢..
Backtracking 标记所有可以到达的值(需要设定一个初始值) 遍历这些可达的值, 如果有值通过-R,+W 后都不可达,即为死锁. 感觉 backtracking 过程中已经可以出结果了.. 吃饭的时候想想 |
 |
13
codecrash 2019-03-13 15:05:05 +08:00
#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; } } } 除了唯一的一个测试用例，其他都过了 |
Select Language