【枚举+O(1)算贡献】CF872div2 C

素颜马尾好姑娘i 2024-03-22 14:26 28阅读 0赞

[Problem - C - Codeforces][]

题意：

有n个人，m个位子

有三种坐法：

1.从左到右坐

2.从右到左坐

3.先坐中间，再坐左边和右边

每一个都是不同的坐法

每个人可以任意顺序排列

问怎么坐能使人数最多

思路：

感觉需要一些想象力

枚举+O(1)算贡献

![a2e21bcf740c4404b2ad63e96aef83da.png][]

Code：

#include <bits/stdc++.h>
    
    #define min(a,b) (a<b?a:b)
    #define int long long
    
    using namespace std;
    
    const int mxn=1e5+10;
    const int mod=1e9+7;
    
    int n,m,x,cnt1=0,cnt2=0;
    int a[mxn];
    
    void solve(){
    	cnt1=cnt2=0;
    	cin>>n>>m;
    	map<int,int> mp;
    	for(int i=1;i<=n;i++){
    		cin>>a[i];
    		if(a[i]==-1) cnt1++;
    		else if(a[i]==-2) cnt2++;
    		else mp[a[i]]++;
    	}
    	int ans=min(m,mp.size()+max(cnt1,cnt2));
    	int cnt=0;
    	for(auto it:mp){
    		int pre=min(it.first-1,cnt+cnt1);
    		int suf=min(m-it.first,mp.size()-cnt+cnt2-1ll);
    		cnt++;
    		ans=max(ans,pre+suf+1);
    	}
    	cout<<ans<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        int __=1;cin>>__;
        while(__--)solve();return 0;
    }

[Problem - C - Codeforces]: https://codeforces.com/contest/1825/problem/C
[a2e21bcf740c4404b2ad63e96aef83da.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/bf86f56aeb74472485ecaf53b487a37c.png

发表评论取消回复

表情：

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

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

相关阅读

相关【枚举区间】CF Edu10 C

[Problem - C - Codeforces][] 题意： ![155e04f8b5114d97a013247f06027577.png][] 思路：应该反思一

落日映苍穹つ/ 2024年03月25日 00:19/ 0 赞/ 79 阅读

相关【枚举gcd】CF803 C

[Problem - C - Codeforces][] 题意： ![c0f74c9a05f2451ead3cf4587dd84218.png][] 思路：要使所有数

落日映苍穹つ/ 2024年03月23日 22:42/ 0 赞/ 57 阅读

相关【枚举】CF1706 C

有人一道1400写了一个小时 [Problem - C - Codeforces][] 题意： ![24af41cf246b45db9ced0751c3617969.p

Myth丶恋晨/ 2024年03月23日 19:27/ 0 赞/ 40 阅读

相关【枚举，构造】CF1582 C D

[Problem - C - Codeforces][] 题意： ![41aba6a6704a46188f11720ce4b622e5.png][] ![35a7376c

旧城等待，/ 2024年03月23日 18:48/ 0 赞/ 72 阅读

相关【枚举+trie+dfs】CF514 C

[Problem - 514C - Codeforces][] 题意： ![5b42449d876c4235a6e81881e28f8ef5.png][] 思路：其实

清疚/ 2024年03月23日 18:05/ 0 赞/ 69 阅读

相关【枚举】CF1833 D

[Problem - D - Codeforces][] 题意：给定一个序列，让你找一个区间，翻转区间内的数，交换前缀和后缀，让结果数组的字典序最大 ![c14db1d

深碍√TFBOYSˉ_/ 2024年03月22日 19:49/ 0 赞/ 78 阅读

相关【二进制枚举+双指针】CF828div2 C. Flexible String

原来Brute Force就是枚举 Brute Force！ [Problem - C - Codeforces][] 题意： ![7141b563d11346efa

深碍√TFBOYSˉ_/ 2024年03月22日 19:17/ 0 赞/ 67 阅读

相关【枚举+O(1)算贡献】CF872div2 C

[Problem - C - Codeforces][] 题意：有n个人，m个位子有三种坐法： 1.从左到右坐 2.从右到左坐 3.先坐中间，再坐左边和右边

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

相关【组合数学算贡献+枚举】CF816div2 C. Monoblock

题解都看了半天才懂 [Problem - C - Codeforces][] 题意： ![82342572fc4d4cdd8ad06219e506c00a.png][]

女爷i/ 2024年03月22日 11:36/ 0 赞/ 65 阅读

相关【贪心（计算贡献）+操作】CF833div2 C. Zero-Sum Prefixes

这道题考虑贪心，计算贡献就好了 [Problem - C - Codeforces][] 题意：定义一个数列的值为前缀和为0的位置个数，每次操作可以把一个ai==0的数

àì夳堔傛蜴生んèń/ 2024年03月22日 06:06/ 0 赞/ 40 阅读