2021年ICPC网络赛A题分析及代码

灰太狼 2022-09-12 05:49 132阅读 0赞

**本文首发于微信公众号："算法与编程之美"，欢迎关注，及时了解更多此系列文章。**

## 思路 ##

读完题后了解题的大意：有k个节点，编号为0 - k-1，每个节点可以在空闲时间处理请求，每个请求的有一个到达时间和处理该请求的持续时间；节点空闲表示当一个请求在达到时间时，该节点未处理任何一个其他请求，即为该节点空闲！第i个请求优先考虑i % k 个节点是否为空，不为空优先考虑i % k, 否则依次后推，(1 + 1) % k, (i + 2) % k，直到找到空闲节点为止。

然后我看了一下数据大小k个节点和n组请求 k, n <= 1^5；以及节点的到达时间和持续时间 <= 1e9; 所以本题涉及的最大数据不会超过2e9！，不会报int；最开始模拟去写，然后tle了，因为最坏的情况时n\*k,我们需要将其控制在nlog(k) 以内；

## 模拟思路1 ##

模拟思路就是去模拟这个过程，优先考虑i%k是否满足，不满足继续后推(i + 1) % k … 如果所有的节点都不满足当前时间为空闲就表示第i个请求不被接收；然而最坏的情况就是每次都没有满足的节点，我们都要去模拟一次整个过程也就是所有节点，单次模拟时间复杂度就是k, 那么n次时间复杂度就是n\*k; n, k <= 1^5, 所以最坏情况必定会tle.

![7f09d46c216570e5dcd7a6c505266ff7.png][]

![aec52861f30130f876f9110fc7b1ed99.png][] 模拟过程，节点1处理了两个请求， 0，2节点各一个，故此1处理请求最多，输出1.

## 线段树优化思路 ##

我们唯一能优化的地方就是单次查找的节点，单次查找满足条件的节点采用线段树去优化，可以将其每次查找的复杂度降低到log(k)级别；线段树优化：线段树优化需要维护一个区间内的最小值(也就是某个节点在最小的时间段空闲)，如果该最小值小于某个请求的到来时间，代表该区间存在一个满足条件的节点能够处理到来的请求；因为考虑道第i个请求的优先选择i%k 节点， 所以我们ask操作时， 区间分别为 (i%k+1 ~ k) 就是i%k的右半部分区间优先考虑，其次左半部分的区间(1 ~ i%k) (注：因为此处是从1 - k，所以i % k应该再加一个1)；

![90c710fe1a9698b80d4c5ee9ebebe971.png][]

依次内推，写出线段树板子即可！

<table> 
 <tbody> 
 <tr> 
 <td style="vertical-align:top;"> #include &lt;iostream&gt; #include &lt;algorithm&gt; #include &lt;cstring&gt; #include &lt;string&gt; #include &lt;queue&gt; #include &lt;vector&gt; #include &lt;cstdio&gt; using namespace std; typedef long long LL; const int N = 100010, INF = 2e9+10; LL a[N], n, k; LL cnt[N]; struct SegmT{ &nbsp;&nbsp;&nbsp;&nbsp;LL l, r; &nbsp;&nbsp;&nbsp;&nbsp;LL val; } tr[N * 4]; void upside(int p){ &nbsp;&nbsp;&nbsp;&nbsp;tr[p].val = min(tr[p * 2].val, tr[p * 2 + 1].val); } void build(LL p, LL l, LL r){ &nbsp;&nbsp;&nbsp;&nbsp;tr[p].l = l, tr[p].r = r; &nbsp;&nbsp;&nbsp;&nbsp;if (l == r) { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;tr[p].val = 0; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;LL mid = (l + r) &gt;&gt; 1; &nbsp;&nbsp;&nbsp;&nbsp;build(p * 2, l, mid); &nbsp;&nbsp;&nbsp;&nbsp;build(p * 2 + 1, mid + 1, r); &nbsp;&nbsp;&nbsp;&nbsp;upside(p); } void change(LL p, LL x, LL v){ &nbsp;&nbsp;&nbsp;&nbsp;if (tr[p].l == tr[p].r){ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;tr[p].val = v; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;LL mid = (tr[p].l + tr[p].r) &gt;&gt; 1; &nbsp;&nbsp;&nbsp;&nbsp;if (x &lt;= mid) change(p * 2, x, v); &nbsp;&nbsp;&nbsp;&nbsp;else change(p * 2 + 1, x, v); &nbsp;&nbsp;&nbsp;&nbsp;upside(p); } LL ask(LL p, LL l, LL r, LL t){ &nbsp;&nbsp;&nbsp;&nbsp;if (tr[p].l == tr[p].r) { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return tr[p].r; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;LL mid = (tr[p].l + tr[p].r) &gt;&gt; 1; &nbsp;&nbsp;&nbsp;&nbsp;LL res = -1; &nbsp;&nbsp;&nbsp;&nbsp;if (l &lt;= mid &amp;&amp; r &gt;= tr[p].l &amp;&amp; tr[p * 2].val &lt;= t){ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;res = ask(p * 2, l, r, t); &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;if( res == - 1 &amp;&amp; r &gt;= mid + 1 &amp;&amp; &nbsp;l &lt;= tr[p].r &amp;&amp; tr[p * 2 + 1].val &lt;= t){ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;res = ask(p * 2 + 1, l, r, t); &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;return res; } int main(){ &nbsp;&nbsp;&nbsp;&nbsp;cin &gt;&gt; k &gt;&gt; n; &nbsp;&nbsp;&nbsp;&nbsp;for (int i = 0; i &lt; N * 4; i ++) tr[i].val = INF; &nbsp;&nbsp;&nbsp;&nbsp;build(1, 1, k); &nbsp;&nbsp;&nbsp;&nbsp;LL res = 0; &nbsp;&nbsp;&nbsp;&nbsp;for (int i = 0; i &lt; n; i ++){ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;LL co, t; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;scanf("%lld %lld", &amp;co, &amp;t); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;LL p = (i % k) + 1; // 当前所取的p值！ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;LL t1 = ask(1, p, k, co); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if (t1 == -1){ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;LL t2 = ask(1, 1, p-1, co); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if (t2 != -1){ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;cnt[t2] ++; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;res = max(res, cnt[t2]); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;change(1, t2, co + t); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;cnt[t1] ++; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;res = max(res, cnt[t1]); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;change(1, t1, co + t); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;bool flag = false; &nbsp;&nbsp;&nbsp;&nbsp;for (int i = 1; i &lt;= k; i ++){ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if (!flag &amp;&amp; cnt[i] == res) { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf("%lld", i-1); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;flag = true; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else if (cnt[i] == res) printf(" %lld", i-1); &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;return 0; } </td> 
 </tr> 
 </tbody> 
</table>

实习编辑：王晓姣

稿件来源：深度学习与文旅应用实验室（DLETA）

[7f09d46c216570e5dcd7a6c505266ff7.png]: /images/20220828/87d3345a90134602b3e6f1bdfcf854bb.png
[aec52861f30130f876f9110fc7b1ed99.png]: /images/20220828/1793e81446734230bef6eae8a6c35e8c.png
[90c710fe1a9698b80d4c5ee9ebebe971.png]: /images/20220828/fbfc2c8c08f9430ca4ab7d8267af7a93.png