【贪心+构造】CF1806B

素颜马尾好姑娘i 2024-03-22 17:17 57阅读 0赞

[? - Virtual Judge (vjudge.net)][- Virtual Judge _vjudge.net]

题意：

给定一个长度为n的数列a，你可以重排这个数列

现在想问你怎么重排可以使得

![8ea107e2af2e48aabf74246a477fae2c.png][]

最小

![56b0679790b9477f9c277fbb13783bb1.png][]

思路：

基于贪心的构造

就0 1 2这么猜过去

当mex=0的时候，应该是0 x 0 x ....这样子构造

但是这样的前提是(N+1)/2>=cnt\_0

当mex=1的时候，避免把0和1搞在一起就行

当所有数都是0的时候，mex=1

否则就是mex=2

Code：

#include <bits/stdc++.h>
    
    #define int long long
    #define max(a,b) (a>b?a:b)
    #define min(a,b) (a<b?a:b)
    
    using namespace std;
    
    const int mxn=3e5+10;
    const int mxe=3e5+10;
    const int mod=1e9+7;
    
    int N;
    int a[mxn];
    
    void solve(){
    	cin>>N;
    	for(int i=1;i<=N;i++) cin>>a[i];
    	int cnt_0=0,ok=0;
    	for(int i=1;i<=N;i++){
    		if(a[i]==0) cnt_0++;
    		if(a[i]>=2) ok=1;
    	}
    	if(cnt_0<=(N+1)/2) cout<<0<<'\n';
    	else if(ok||cnt_0==N) cout<<1<<'\n';
    	else cout<<2<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        int __=1;cin>>__;
        while(__--)solve();return 0;
    }

[- Virtual Judge _vjudge.net]: https://vjudge.net/contest/558206#problem/A
[8ea107e2af2e48aabf74246a477fae2c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/4b0bbbdcc77f4e1e8e6e4941893d11f4.png
[56b0679790b9477f9c277fbb13783bb1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/0e54abf2b85f4f60a77d5316326aac0c.png

发表评论取消回复

表情：

评论列表（有 0 条评论，57人围观）

还没有评论，来说两句吧...

相关阅读

相关【反悔贪心】CF1278B CF11B

[Problem - 1278B - Codeforces][] 题意： ![c0fbd2f3d4224469b8dd5bb7d049f4ee.png][] 思路： !

以你之姓@/ 2024年03月24日 18:30/ 0 赞/ 91 阅读

相关【贪心】CF1822 E

[Problem - 1822E - Codeforces][] 题意： ![2e9c008736434bd3aade35f13ba3671b.png][] ![e793

女爷i/ 2024年03月23日 23:48/ 0 赞/ 88 阅读

相关【贪心】CF1841 D

[Codeforces][] 题意： ![f231a62f84944973acc878c8bcd43a09.png][] ![eed5aa21f67e4bf8a27aad

绝地灬酷狼/ 2024年03月23日 23:24/ 0 赞/ 70 阅读

相关【贪心+构造】CF1806B

[? - Virtual Judge (vjudge.net)][- Virtual Judge _vjudge.net] 题意：给定一个长度为n的数列a，你可以重排这个

素颜马尾好姑娘i/ 2024年03月22日 17:17/ 0 赞/ 58 阅读

相关【数论+构造】CF752div1 B

[Problem - 1603B - Codeforces][] 题意：给定两个数x,y，让你构造一个n使得n%x=y%n 其中1<=n<=2e18 思路：因为是

向右看齐/ 2024年03月22日 13:57/ 0 赞/ 92 阅读

相关【构造排列】CF869div2 B

[Problem - 1818B - Codeforces][] 题意： ![db00d9d113894bbc8977f4c8a2ddbe63.png][] 思路：对

谁借莪１个温暖的怀抱￠/ 2024年03月22日 11:52/ 0 赞/ 73 阅读

相关【贪心】CF1845 C

[Problem - C - Codeforces][] 题意： ![462238034546493bae4dc73170075b68.png][] ![9ad694f7

深藏阁楼爱情的钟/ 2024年03月17日 16:31/ 0 赞/ 63 阅读

相关【Tree树上染色+贪心】CF1387B1

[Problem - 1387B1 - Codeforces][] 题意： ![946309f0da624ae09c2715a343db0b1d.png][] ![0a3

柔光的暖阳◎/ 2024年03月16日 07:40/ 0 赞/ 52 阅读

相关贪心——cf708b

先求0，1的个数，然后贪心输出01即可 include<bits/stdc++.h> using namespace std; define ll l

朴灿烈づ我的快乐病毒、/ 2023年10月12日 08:21/ 0 赞/ 39 阅读

相关 CF685B Kay and Snowflake 贪心

CF685B Kay and Snowflake 链接 [CF][] 题目大意给你一颗树，询问子树的重心思路贪心？重心肯定是向上走的，所

た入场券/ 2021年11月01日 10:16/ 0 赞/ 254 阅读