题目大意
给定一个数组，通过若干次“除以 2 取整”的操作把元素压到一定范围内，要求最终能覆盖 0 到 x-1 的所有数（每个数至少出现一次），求最大的可行 x。通常用二分答案 + 贪心检查。
AC 代码 二分答案 相比于那个过了93.33%的还是修改了很多。
总体的check函数的贪心思路是 ≥x 的没用，之前就到过的（vis中有的）也没用。
没用，那怎么让他有用那？那当然是>>1才有用，不断的>>1，直到有用（注意条件，不要死循环了）。
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=71786526
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
50
| #include <iostream>
#include <vector>
#include <bitset>
#include <algorithm>
#include <set>
using namespace std;
const int maxn=1e5+7,maxA=static_cast<int>(1e6)+7;
int n,t,a[maxA],A;
set<int> vis;
inline bool check(int x) {
for(int i=n;i>=1;i--) {
int ai=a[i];
while(ai>=x)
ai>>=1;
while(vis.count(ai)!=0 && ai!=0)
ai>>=1;
vis.insert(ai);
}
for(int i=0;i<=x-1;i++) {
if(vis.count(i)==0)
return false;
}
return true;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>t;
for(int _=1;_<=t;_++) {
cin>>n;
for(int i=1;i<=n;i++) {
cin>>a[i];
}
sort(&a[1],&a[n+1],less<int>());
int l=0,r=n+1;
while(l<r) {
vis.clear();
int mid=l+r+1>>1;
if(check(mid)) l=mid;
else r=mid-1;
}
cout<<l<<endl;
}
return 0;
}
|
TLE pass 2/30
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
| #include <iostream>
#include <vector>
#include <bitset>
#include <algorithm>
using namespace std;
const int maxn=1e5+7,maxA=static_cast<int>(1e6)+7;
int n,t,a[maxA],A;
bitset<maxA> ovis,vis;
inline bool check(int x) {
for(int i=n;i>=1;i--) {
int ai=a[i];
if(ai<x)
break;
while(ai>>=1) {
if(!vis[ai] && ai<x) {vis[ai]=true;break;}
}
}
for(int i=1;i<=x-1;i++) {
if(!vis[i])
return false;
}
return true;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>t;
for(int _=1;_<=t;_++) {
cin>>n;
vis.reset();ovis.reset();
for(int i=1;i<=n;i++) {
cin>>a[i];A=max(A,a[i]);ovis[a[i]]=true;
}
sort(&a[1],&a[n+1],less<int>());
int l=0,r=A;
while(l<r) {
for(int i=1;i<=A;i++)
vis[i]=ovis[i];
int mid=l+r+1>>1;
if(check(mid)) l=mid;
else r=mid-1;
}
cout<<l<<endl;
}
return 0;
}
|
int l=0,r=n+1; // 如果n个数连续，那么就是n
for(int i=1;i<=n+1;i++)
vis[i]=ovis[i];
把上界换成n+1过了53.33% https://ac.nowcoder.com/acm/contest/view-submission?submissionId=71785676
但出现了WA
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
| #include <iostream>
#include <vector>
#include <bitset>
#include <algorithm>
using namespace std;
const int maxn=1e5+7,maxA=static_cast<int>(1e6)+7;
int n,t,a[maxA],A;
bitset<maxA> ovis,vis;
inline bool check(int x) {
for(int i=n;i>=1;i--) {
int ai=a[i];
if(ai<x)
break;
while(ai>>=1) {
if(!vis[ai] && ai<x) {vis[ai]=true;break;}
}
}
for(int i=1;i<=x-1;i++) {
if(!vis[i])
return false;
}
return true;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>t;
for(int _=1;_<=t;_++) {
cin>>n;
vis.reset();ovis.reset();
for(int i=1;i<=n;i++) {
cin>>a[i];ovis[a[i]]=true;
}
sort(&a[1],&a[n+1],less<int>());
int l=0,r=n+1;
while(l<r) {
for(int i=1;i<=n+1;i++)
vis[i]=ovis[i];
int mid=l+r+1>>1;
if(check(mid)) l=mid;
else r=mid-1;
}
cout<<l<<endl;
}
return 0;
}
|
WA pass93.33% https://ac.nowcoder.com/acm/contest/view-submission?submissionId=71785979
应该是快了
增加了
1
2
3
4
| for(int i=2;i<=n;i++) {
if(a[i]>=x) break;
if(a[i]==a[i-1]) vis[0]=true;break;
}
|
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
50
51
52
53
54
55
56
57
| #include <iostream>
#include <vector>
#include <bitset>
#include <algorithm>
using namespace std;
const int maxn=1e5+7,maxA=static_cast<int>(1e6)+7;
int n,t,a[maxA],A;
bitset<maxA> ovis,vis;
inline bool check(int x) {
for(int i=2;i<=n;i++) {
if(a[i]>=x) break;
if(a[i]==a[i-1]) vis[0]=true;break;
}
for(int i=n;i>=1;i--) {
int ai=a[i];
if(ai<x)
break;
while(true) {
ai>>=1;
if(!vis[ai] && ai<x) {vis[ai]=true;break;}
if(ai==0)
break;
}
}
for(int i=0;i<=x-1;i++) {
if(!vis[i])
return false;
}
return true;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>t;
for(int _=1;_<=t;_++) {
cin>>n;
vis.reset();ovis.reset();
for(int i=1;i<=n;i++) {
cin>>a[i];ovis[a[i]]=true;
}
sort(&a[1],&a[n+1],less<int>());
int l=0,r=n+1;
while(l<r) {
for(int i=0;i<=n+1;i++)
vis[i]=ovis[i];
int mid=l+r+1>>1;
if(check(mid)) l=mid;
else r=mid-1;
}
cout<<l<<endl;
}
return 0;
}
|