• 周五. 7月 1st, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

[hdu7034]Array

admin

11月 28, 2021

令$f(a)_{i}=min_{i<jle n,a_{i}=a_{j}}j$​​(特别的,若不存在$j$​​则令$f(a)_{i}=n+1$​​),则有以下性质:

1.对于$b_{i}$​​​​​​​,存在$a_{i}$​​​​​​​使得$f(a)=b$​​​​,当且仅当$i<b_{i}$​​​​且不为$n+1$的$b_{i}$互不相同(以下称这样的$b_{i}$​​​​​​​合法)

2.合法的$b_{i}$​可以唯一确定$a_{i}$​​(仅关心权值是否相同,即$a_{i}
e a’_{i}$当且仅当$exists i
e j,[a_{i}=a_{j}]
e [a’_{i}=a’_{j}]$)

通过这两个性质,问题即判定是否存在合法的$b_{i}$,使得其(唯一)对应的$a_{i}$满足题中的条件

而题中的条件从$b_{i}$​​​的角度来看,实际上是这样的:令$forall 1le i<n,B_{i+1}=max(B_{i},b_{i})$且$B_{1}$为最后一个之前没有出现过的数位置,也即$max_{1le ile n且forall 1le jle n,b_{j}
e i}i$

考虑从后往前贪心确定$b_{i}$​​(其中$1le i<n$​​),并维护以下两个集合:

1.$A_{0}$​​表示强制存在的元素(初始为$(B_{1},n]$​​​,若$b_{i}in A_{0}$则将其从$A_{0}$​中删除)

2.$A_{1}$表示允许存在的元素(初始为$[1,B_{1})cup{n+1}$,若$b_{i}in A_{1}$且$b_{i}le n$则将其从$A_{1}$中删除)

下面,再分类讨论:

1.若$B_{i}<B_{i+1}$​,则$b_{i}=B_{i+1}$​(注意判定$b_{i}>i$)

2.若$B_{i}=B_{i+1}$​,则要求$i<b_{i}le B_{i}$​,注意到该区间的左端点单调递增,因此用set维护$A_{0}$​和$A_{1}$​,分别不断删除最小值(若删除$A_{0}$​的最小值则无解)直至最小值$>i$​​

进一步的,再分类讨论:

(1)若两者的最小值都不能选择,则无解(还有$le B_{i}$​的限制)

(2)若只有一个最小值可以选择,显然选择该最小值即可

(3)若两个最小值都可以选择,设分别为$x$和$y$,将两者的都删除并将$max(x,y)$加入$A_{1}$​

关于(3)的解释:注意到右端点单调不下降,因此最终$min(x,y)$​能选择那么$max(x,y)$​一定能选择

若$x<y$​​显然可以这样贪心,若$x>y$​​即要求$x=max(x,y)$​​一定被选择,如果最终$x$​​被选择显然没有影响,若未被选择那么不妨将$b_{i}$​​修改为$x$​​​即可

(注意特判$B_{1}>n$的情况)

由此维护即可,时间复杂度为$o(nlog n)$,可以通过

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define N 200005
 4 set<int>A0,A1;
 5 int t,n,B[N];
 6 void del(int x){
 7     if (x>n)return;
 8     if (A0.find(x)!=A0.end())A0.erase(x);
 9     else A1.erase(x);
10 }
11 int main(){
12     scanf("%d",&t);
13     while (t--){
14         scanf("%d",&n);
15         for(int i=1;i<=n;i++)scanf("%d",&B[i]);
16         bool flag=(B[1]>n);
17         for(int i=1;i<=n;i++)
18             if (B[i]<i){
19                 flag=1;
20                 break;
21             }
22         if (flag){
23             printf("NO
");
24             continue;
25         }
26         A0.clear(),A1.clear();
27         for(int i=B[1]+1;i<=n;i++)A0.insert(i);
28         for(int i=1;i<B[1];i++)A1.insert(i);
29         A1.insert(n+1);
30         for(int i=1;i<n;i++){
31             if (B[i]<B[i+1])del(B[i+1]);
32             else{
33                 if ((!A0.empty())&&((*A0.begin())<=i)){
34                     flag=1;
35                     break;
36                 }
37                 while ((*A1.begin())<=i)A1.erase(A1.begin());
38                 int x=0,y=(*A1.begin());
39                 if ((!A0.empty())&&((*A0.begin())<=B[i]))x=(*A0.begin());
40                 if (y>B[i])y=0;
41                 if ((!x)&&(!y)){
42                     flag=1;
43                     break;
44                 }
45                 if (x)del(x);
46                 if (y)del(y);
47                 if ((x)&&(y))A1.insert(max(x,y));
48             }
49         }
50         if (!A0.empty())flag=1;
51         if (flag)printf("NO
");
52         else printf("YES
");
53     }
54     return 0;
55 } 

View Code

发表评论

您的电子邮箱地址不会被公开。