|
|
<mxfile host="Electron" modified="2023-08-23T00:51:45.678Z" agent="Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) draw.io/21.3.7 Chrome/112.0.5615.204 Electron/24.5.0 Safari/537.36" etag="smbT_BMNePP6TkLC_DvL" version="21.3.7" type="device">
|
|
|
<diagram id="K-rnQcr-T-lCCHxmAbID" name="第 1 页">
|
|
|
<mxGraphModel dx="1418" dy="838" grid="1" gridSize="10" guides="1" tooltips="1" connect="1" arrows="1" fold="1" page="1" pageScale="1" pageWidth="827" pageHeight="1169" math="0" shadow="0">
|
|
|
<root>
|
|
|
<mxCell id="0" />
|
|
|
<mxCell id="1" parent="0" />
|
|
|
<mxCell id="cCYWK_54qTLuP-upu6Tg-1" value="1" style="rounded=0;whiteSpace=wrap;html=1;fontSize=18;fillColor=#fff2cc;strokeColor=#d6b656;" parent="1" vertex="1">
|
|
|
<mxGeometry x="70" y="60" width="60" height="60" as="geometry" />
|
|
|
</mxCell>
|
|
|
<mxCell id="cCYWK_54qTLuP-upu6Tg-2" value="0" style="rounded=0;whiteSpace=wrap;html=1;fontSize=18;fillColor=#fff2cc;strokeColor=#d6b656;" parent="1" vertex="1">
|
|
|
<mxGeometry x="130" y="60" width="60" height="60" as="geometry" />
|
|
|
</mxCell>
|
|
|
<mxCell id="cCYWK_54qTLuP-upu6Tg-3" value="0" style="rounded=0;whiteSpace=wrap;html=1;fontSize=18;fillColor=#fff2cc;strokeColor=#d6b656;" parent="1" vertex="1">
|
|
|
<mxGeometry x="190" y="60" width="60" height="60" as="geometry" />
|
|
|
</mxCell>
|
|
|
<mxCell id="cCYWK_54qTLuP-upu6Tg-4" value="0" style="rounded=0;whiteSpace=wrap;html=1;fontSize=18;fillColor=#fff2cc;strokeColor=#d6b656;" parent="1" vertex="1">
|
|
|
<mxGeometry x="250" y="60" width="60" height="60" as="geometry" />
|
|
|
</mxCell>
|
|
|
<mxCell id="cCYWK_54qTLuP-upu6Tg-5" value="1" style="rounded=0;whiteSpace=wrap;html=1;fontSize=18;fillColor=#fff2cc;strokeColor=#d6b656;" parent="1" vertex="1">
|
|
|
<mxGeometry x="310" y="60" width="60" height="60" as="geometry" />
|
|
|
</mxCell>
|
|
|
<mxCell id="cCYWK_54qTLuP-upu6Tg-6" value="1" style="rounded=0;whiteSpace=wrap;html=1;fontSize=18;fillColor=#f5f5f5;fontColor=#333333;strokeColor=#666666;" parent="1" vertex="1">
|
|
|
<mxGeometry x="370" y="60" width="60" height="60" as="geometry" />
|
|
|
</mxCell>
|
|
|
<mxCell id="cCYWK_54qTLuP-upu6Tg-7" value="0" style="rounded=0;whiteSpace=wrap;html=1;fontSize=18;fillColor=#f5f5f5;fontColor=#333333;strokeColor=#666666;" parent="1" vertex="1">
|
|
|
<mxGeometry x="430" y="60" width="60" height="60" as="geometry" />
|
|
|
</mxCell>
|
|
|
<mxCell id="cCYWK_54qTLuP-upu6Tg-8" value="0" style="rounded=0;whiteSpace=wrap;html=1;fontSize=18;fillColor=#f5f5f5;fontColor=#333333;strokeColor=#666666;" parent="1" vertex="1">
|
|
|
<mxGeometry x="490" y="60" width="60" height="60" as="geometry" />
|
|
|
</mxCell>
|
|
|
<mxCell id="cCYWK_54qTLuP-upu6Tg-9" value="1" style="rounded=0;whiteSpace=wrap;html=1;fontSize=18;fillColor=#f5f5f5;fontColor=#333333;strokeColor=#666666;" parent="1" vertex="1">
|
|
|
<mxGeometry x="550" y="60" width="60" height="60" as="geometry" />
|
|
|
</mxCell>
|
|
|
<mxCell id="cCYWK_54qTLuP-upu6Tg-10" value="0" style="rounded=0;whiteSpace=wrap;html=1;fontSize=18;fillColor=#f5f5f5;fontColor=#333333;strokeColor=#666666;" parent="1" vertex="1">
|
|
|
<mxGeometry x="610" y="60" width="60" height="60" as="geometry" />
|
|
|
</mxCell>
|
|
|
<mxCell id="cCYWK_54qTLuP-upu6Tg-11" value="x=3,找出连续3个空房间及以上的开始位置" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;fontSize=20;fontStyle=1" parent="1" vertex="1">
|
|
|
<mxGeometry x="155" y="20" width="490" height="30" as="geometry" />
|
|
|
</mxCell>
|
|
|
<mxCell id="cCYWK_54qTLuP-upu6Tg-13" value="tr[u].mx=3,tr[u].lx=0,tr[u].rx=1" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;fontSize=18;fontStyle=1" parent="1" vertex="1">
|
|
|
<mxGeometry x="90" y="120" width="570" height="30" as="geometry" />
|
|
|
</mxCell>
|
|
|
<mxCell id="cCYWK_54qTLuP-upu6Tg-14" value="1" style="rounded=0;whiteSpace=wrap;html=1;fontSize=18;fillColor=#dae8fc;strokeColor=#6c8ebf;" parent="1" vertex="1">
|
|
|
<mxGeometry x="80" y="270" width="60" height="60" as="geometry" />
|
|
|
</mxCell>
|
|
|
<mxCell id="cCYWK_54qTLuP-upu6Tg-15" value="0" style="rounded=0;whiteSpace=wrap;html=1;fontSize=18;fillColor=#dae8fc;strokeColor=#6c8ebf;" parent="1" vertex="1">
|
|
|
<mxGeometry x="140" y="270" width="60" height="60" as="geometry" />
|
|
|
</mxCell>
|
|
|
<mxCell id="cCYWK_54qTLuP-upu6Tg-16" value="0" style="rounded=0;whiteSpace=wrap;html=1;fontSize=18;fillColor=#dae8fc;strokeColor=#6c8ebf;" parent="1" vertex="1">
|
|
|
<mxGeometry x="200" y="270" width="60" height="60" as="geometry" />
|
|
|
</mxCell>
|
|
|
<mxCell id="cCYWK_54qTLuP-upu6Tg-17" value="0" style="rounded=0;whiteSpace=wrap;html=1;fontSize=18;fillColor=#fff2cc;strokeColor=#d6b656;" parent="1" vertex="1">
|
|
|
<mxGeometry x="260" y="270" width="60" height="60" as="geometry" />
|
|
|
</mxCell>
|
|
|
<mxCell id="cCYWK_54qTLuP-upu6Tg-18" value="1" style="rounded=0;whiteSpace=wrap;html=1;fontSize=18;fillColor=#fff2cc;strokeColor=#d6b656;" parent="1" vertex="1">
|
|
|
<mxGeometry x="320" y="270" width="60" height="60" as="geometry" />
|
|
|
</mxCell>
|
|
|
<mxCell id="cCYWK_54qTLuP-upu6Tg-19" value="tr[u].mx=3,tr[u].lx=0,tr[u].rx=0" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;fontSize=18;" parent="1" vertex="1">
|
|
|
<mxGeometry x="95" y="340" width="270" height="30" as="geometry" />
|
|
|
</mxCell>
|
|
|
<mxCell id="cCYWK_54qTLuP-upu6Tg-20" value="" style="shape=flexArrow;endArrow=classic;html=1;rounded=0;fontSize=18;entryX=0.644;entryY=0.011;entryDx=0;entryDy=0;entryPerimeter=0;fillColor=#f8cecc;strokeColor=#b85450;" parent="1" edge="1">
|
|
|
<mxGeometry width="50" height="50" relative="1" as="geometry">
|
|
|
<mxPoint x="240" y="210" as="sourcePoint" />
|
|
|
<mxPoint x="238.64" y="260.65999999999997" as="targetPoint" />
|
|
|
</mxGeometry>
|
|
|
</mxCell>
|
|
|
<mxCell id="cCYWK_54qTLuP-upu6Tg-21" value="此时，mid=1+5 &gt;&gt;1 =3:<br><br>(1) tr[ls].mx=2&nbsp;不够3个，不能走这个分支<br><br>(2) tr[ls].rx+tr[rs].lx=3&nbsp;够了，走这个分支&nbsp; =&gt; return mid-tr[ls].rx+1,即可获得位置2，这个分支不是递归，而是实实在在的返回真实值<br><div style=""><span style="background-color: initial;"><br></span></div><div style=""><span style="background-color: initial;">(3) tr[rs].mx&gt;=x这个分支没机会走</span></div>" style="text;html=1;strokeColor=none;fillColor=none;align=left;verticalAlign=middle;whiteSpace=wrap;rounded=0;fontSize=18;fontStyle=1" parent="1" vertex="1">
|
|
|
<mxGeometry x="80" y="390" width="650" height="170" as="geometry" />
|
|
|
</mxCell>
|
|
|
<mxCell id="cCYWK_54qTLuP-upu6Tg-22" value="tr[ls].mx&gt;=3，由于想获取尽量小的左起点，而左半边够用，向左递归" style="text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;fontSize=18;fontStyle=1" parent="1" vertex="1">
|
|
|
<mxGeometry x="85" y="170" width="570" height="30" as="geometry" />
|
|
|
</mxCell>
|
|
|
<mxCell id="cCYWK_54qTLuP-upu6Tg-23" value="<font style="font-size: 27px;">总结：<br></font><br>（1）符合要求的状态，共三种情况:<br><span style=""></span>&nbsp; &nbsp; &nbsp;① 左半部分存在大于等于x的空白房间<br>&nbsp; &nbsp; &nbsp;② 左半部分后面+右半部分前面存在大于等于x的空白房间<br>&nbsp; &nbsp; &nbsp;③ 右半部分存在大于等于x的空白房间<br><br>这三种情依次讨论一遍，就可以求出最左侧的起点位置。<br><br>（2）左半部分 或&nbsp;右半部分中存在解，但无法确定具体位置，就还需要继续递归求解。<br><br>（3）如果在中间部分存在解，就可以直接找到起点。<br><br>" style="text;html=1;strokeColor=none;fillColor=none;align=left;verticalAlign=middle;whiteSpace=wrap;rounded=0;fontSize=18;fontColor=#FF0A2B;fontStyle=1" parent="1" vertex="1">
|
|
|
<mxGeometry x="80" y="680" width="775" height="140" as="geometry" />
|
|
|
</mxCell>
|
|
|
</root>
|
|
|
</mxGraphModel>
|
|
|
</diagram>
|
|
|
</mxfile>
|
