1、批量初始化次数
某部门在开发一个代码分析工具，需要分析代码模块之间的依赖关系，用来确定模块的初始化顺序、是否有循环依赖等问题。"批量初始化"是指一次可以初始化一个或多个模块，例如模块1依赖模块2、模块3也依赖模块2，但模块1和3没有依赖关系。则必须先"批量初始化"模块2，再"批量初始化"模块1和3。现给定一组模块间的依赖关系请计算需要"批星初始化"的次数。
输入
- 第1行只有一个数字,表示模块总数N。
- 随后的N行依次表示模块1到N的依赖数据。每行的第1个数据表示依赖的模块数量(不会超过N)，之后的数字表示当前模块依赖的模块ID序列,该序列不会重复出现相同的数字模块ID的取值一定在[1,N]之内。
- 模块总数N取值范围 1<=N<=1000。
- 每一行里面的数字按1个空格分隔。
输出
输出"批量初始化次数"，若有循环依赖无法完成初始化，则输出-1。
样例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| 输入：
5
3 2 3 4
1 5
1 5
1 5
0
输出：
3
提示：共5个模块。模块1依赖模块2、3、4；模块2依赖模块5；模块3依赖模块5；模块4依赖模块5；模块5没有依赖任何模块。
批量初始化顺序为{5}->{2,3,4}->{1}，共需"批量初始化"3次。
输入：
3
1 2
1 3
1 1
输出：
-1
提示：存在循环依赖，无法完成初始化，返回-1。
|
解答
不难想到使用拓扑排序解决。一个模块依赖于另一个模块意味着这两个模块不能同时初始化。如果找出一条有向路径，那么这条路径上前面的节点必须先于后面节点的初始化。因此，这道题本质上是求：
有向无环图DAG上的最长路。
这是一个经典的动态规划问题，此处不赘述。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| # include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=10004;
vector<int>g[N];
int in[N],n,m,x,d[N];
int topo(){
queue<int>q;
for(int i=1;i<=n;i++){
if(in[i]==0) q.push(i),d[i]=1;
}
int c=0;
while(!q.empty()){
int u=q.front();q.pop();
++c;
for(int v:g[u]){
d[v]=max(d[v],d[u]+1);
if(--in[v]==0) q.push(v);
}
}
if(c!=n) return -1;
else return *max_element(d+1,d+n+1);
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&m);
in[i]=m;
for(int j=1;j<=m;j++){
scanf("%d",&x);
g[x].push_back(i);
}
}
int ans=topo();
printf("%d\n",ans);
}
|
2、分配资源ID
给定一个管理ID的资源池，可以从资源池中分配资源ID和释放资源ID，分配方式有动会正态分配和指定分配，动态分配是从资源池的开始分配一个资源D，指定分配是指定个资源ID进行分配，无论哪种分配方式释放资源ID时都需要放到资源池的尾部。执行系列操作后，请问资源池的第一个空闲资源ID应该是多少？
注意： 资原池的初始顺序是从小到大。
源池中空闲资源ID不足时，动态分配失败，对资源池不进行任何操作。
指定分配资源ID已经被占用或者不在资源池范围内时，对资源池不进行任何操作。
释放资源ID不在资源池范围内时或者已经是空闲资源ID时，对资源池不进行任何操作。
保证每个用例最后都有空闲资源ID。
输入
第一行是资源池的范围； 第二行是操作个数。
第三行开始，第一个数字代表操作类型，1表示动态分配，2表示指定分配，3表示释放；
如果第一个数字是1，第一个表示分配的个数；
如果第一个数字是2，第二个表示分配的资源ID；
如果第一个数字是3，第二个表示释放的资源ID，
输出
资源池的第一个空闲资源ID。
样例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| 输入：
1 3
2
1 1
3 1
输出：
2
提示：第一行资源池范围是[1,3]，资源池的初始顺序是1->2->3。
第二行操作个数有2个。
第三行动态分配1个资源ID，资源池中剩余的资源ID顺序是2->3。
有四行释放1个资源ID，资源ID是1，资源池中剩余的资源ID顺序是2->3->1。
执行以上操作后，资源池的第一个空闲资源ID是2。
输入：
1 3
3
2 2
3 2
1 1
输出：
-1
提示：第一行行资源池范围是[1,3]，资源池的初始顺序是1->2->3。
第二行操作个数有3个。
第三行指定分配1个资源ID，资源ID是2，资源池中剩余的资源ID顺序是1->3。
第四行释放1个资源ID，资源ID是2，资源池中剩余的资源ID顺序是1->3->2。
第五行动态分配1个资源ID，分配的资源D是1，资源池中剩余的资源ID顺序是3->2。
执行以上操作后，资源池的第一个空闲资源ID是3。
|
提示
保证输入的操作都是合法的。 操作类型范围是[1,3]。
分配次数范围是[1,100000]。
解答
由于给定的是一个区间，我们将这个区间挪到\([1,n]\)中方便我们进行处理，从而得到一个偏移值。在最终输出答案时，我们需要将这个偏移值加回去即可。
那么我们使用二元组有序集<时间戳，资源ID>来保持这个队列的有序性，并用一个数组pos来标识资源ID目前被释放后的时间戳。通过暴力维护这两个信息从而保证每个资源ID能够被正确地删除即可。整个算法的时间复杂度为\(O(n\log n)\)。
这题还可以使用链表解决，不过我对链表操作不熟悉，所以使用set来求解。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| # include <bits/stdc++.h>
# define X first
# define Y second
using namespace std;
typedef long long ll;
const int N=100004;
set<pair<int,int>>st;
int pos[N],tot=0;
int main(){
int n,q,o,x,l,r;
scanf("%d %d %d",&l,&r,&q);
n=r-l+1;
for(int i=1;i<=n;i++)
st.insert(make_pair(i,i)),pos[i]=i;
tot=n;
while(q--){
scanf("%d %d",&o,&x);
x-=l-1;
if(o==1){
if(st.size()>=x){
for(int i=0;i<x;i++){
auto pa=*st.begin();
st.erase(pa);
pos[pa.Y]=0;
}
}
}
else if(o==2){
if(1<=x&&x<=n&&pos[x]!=0){
st.erase(make_pair(pos[x],x));
pos[x]=0;
}
}
else{
if(1<=x&&x<=n&&pos[x]==0){
pos[x]=++tot;
st.insert(make_pair(pos[x],x));
}
}
}
printf("%d\n",st.begin()->Y+l-1);
}
|
3、疯长的草
将种不同的草随机种在一块广漠无垠的二维平面上（直角坐标系内），给定二维数组points表示第0天所有草的初始位置，第i项
points[i]=[xi, yi]表第0天草i在点[xi,
yi]。每天，被草覆盖的点会向外蔓延到它上、下，左、右，左上、左下、右上、右下8个邻居点，注意，初始状态下，可能有多种草在同一点上。
现给定一个整数M，问最小需要多少天，方能找到一点同时至少有M种草？
输入
第一行输入整数M。（2<= M <= n） 第二行输入草的种数n。(2 <= n
<= 50) 后面连续n行输入草初始位置[xi, yi]。(<= xi, vi <=
10^9)
输出
返口找到一点至少生长M种草的最少天数，找不到返回0
样例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| 输入：
2
2
2 1
6 2
输出：
2
提示：在第2天，点(4,0)、(4,1)、(4,2)与(4,3)将有2种草。
输入：
2
3
2 1
6 2
100 100
输出：
2
|
提示
n = points.length 2 <= n <= 50 points[i].length = 2
解答
如果第\(n\)天已经满足了有\(m\)棵草在同一位置上，那么第\(n+1\)天也必定满足这个条件。这启发我们可以使用二分法解决这个问题。
如何判断第\(d\)天存不存在一个点被覆盖了\(m\)次？我们可以观察到到，第\(m\)天后第\(i\)种草所覆盖的位置是一个正方形，这个正方形的左下角和右上角的坐标分别为\((x_i-d,y_i-d),(x_i+d,y_i+d)\)，我们构造出来了\(d\)天后每种草的覆盖情况。
那么为了进行判断，最暴力的方法则是开辟一个二维数组，对于第\(i\)种草，将正方形以内\((x_i-d,y_i-d),(x_i+d,y_i+d)\)的所有点都进行标记一次。这将会导致时间复杂度过大（不过在这题，由于\(n\le
50\)，可以忽略这个问题）。为此，我们可以引用二维前缀和进行优化，防止所有点都被遍历\(n\)次。
此外我们还注意到，坐标的范围达到了惊人的\(10^9\)，为了能够表示上面这些正方形的边界信息，我们需要对这些坐标进行离散化，才能够完成上述直接在二维数组中进行标记的做法。为了保证边界的正确性，我们使用左闭右开的方式精准表示每个正方形离散化后的边界。
最终，完成本题的时间复杂度为\(O(n^2\log
n\cdot \log M)\)，其中\(M\)是潜在的最大天数。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| # include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=54;
struct P{
int lx,rx,ly,ry;
}g[54];
int x[N],y[N],m,n;
int s[N+N][N+N];
bool ok(int d){
memset(s,0,sizeof(s));
map<int,int>mx,my;
for(int i=1;i<=n;i++){
g[i]=P{x[i]-d,x[i]+d+1,y[i]-d,y[i]+d+1};
mx[g[i].lx]=mx[g[i].rx]=0;
my[g[i].ly]=my[g[i].ry]=0;
}
int r=0,c=0;
for(auto it=mx.begin();it!=mx.end();it++) it->Y=++r;
for(auto it=my.begin();it!=my.end();it++) it->Y=++c;
for(int i=1;i<=n;i++){
int lx=mx[g[i].lx];
int rx=mx[g[i].rx];
int ly=my[g[i].ly];
int ry=my[g[i].ry];
++s[lx][ly];++s[rx][ry];
--s[lx][ry];--s[rx][ly];
}
for(int i=1;i<=r;i++){
for(int j=1;j<=c;j++){
s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
if(s[i][j]>=m) return 1;
}
}
return 0;
}
int main(){
scanf("%d %d",&m,&n);
for(int i=1;i<=n;i++)
scanf("%d %d",&x[i],&y[i]);
int l=0,r=1e9;
while(l<r){
int mid=(l+r)>>1;
if(ok(mid)) r=mid;
else l=mid+1;
}
printf("%d\n",l);
}
|