Codeforces Global Round 24 C. Doremy‘s City Construction

àì夳堔傛蜴生んèń 2024-03-30 17:38 56阅读 0赞

[Problem - C - Codeforces][]

题意：

给定n个点，然后连边，当a\[i\]<=a\[j\]<=a\[k\]时不能连，否则可以

问你最多连多少边

思路：

手动模拟一下可知，有些点在凹处，有些点在凸处，因此可以把结点划分成两种，所以这个图就是二分图

答案就是这个二分图里最多连边，肯定是左右两边连起来，因此答案就是乘积

那么哪些点是1哪些点是0我们不知道

因此我们取枚举分界线就好了，然后记录最大值

记得特殊情况的特判

当所有元素都是一样时，就不是二分图，此时边数为n/2

Code：

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    const int mxn=2e5+10;
    map<int,int> mp;
    int n,m;
    int a[mxn],sum[mxn];
    void solve(){
        memset(sum,0,sizeof(sum));
        mp.clear();
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i],mp[a[i]]++;
        sort(a+1,a+1+n);
        int len=unique(a+1,a+1+n)-(a+1);
        if(len==1){
            cout<<n/2<<'\n';
            return;
        }
        for(int i=1;i<=len;i++) sum[i]=sum[i-1]+mp[a[i]];
        int ans=-1;
        for(int i=1;i<=len;i++){
            ans=max(ans,sum[i]*(n-sum[i]));
        }
        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/1764/problem/C

发表评论取消回复

表情：

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

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

相关阅读

相关 Codeforces Round #826 (Div. 3) C

[Problem - C - Codeforces][] 题意：给定一个长度为n的数组，求将该数组分为连续的几个部分，使得每一部分内部的和相同。求分完后每一部分的最大值最

「爱情、让人受尽委屈。」/ 2024年03月31日 13:58/ 0 赞/ 69 阅读

相关 Codeforces Global Round 24 C. Doremy‘s City Construction

[Problem - C - Codeforces][] 题意：给定n个点，然后连边，当a\[i\]<=a\[j\]<=a\[k\]时不能连，否则可以问你最多连多少边

àì夳堔傛蜴生んèń/ 2024年03月30日 17:38/ 0 赞/ 57 阅读

相关 codeforces C. Flower City Fence

codeforces C. Flower City Fence 关键点在于：度与长度为x的围栏饭庄过后相当于对\[1,x\]长度的翻转后的围栏+1。此时运用差分简化

悠悠/ 2023年10月15日 10:31/ 0 赞/ 124 阅读

相关 Codeforces Round 71

第一题：读题+基础贪心 [http://codeforces.com/contest/1207][http_codeforces.com_contest_1207] 第二题

「爱情、让人受尽委屈。」/ 2023年08月17日 16:26/ 0 赞/ 140 阅读

相关 Codeforces Round #729 (Div. 2) c题

[https://codeforces.com/contest/1542/problem/C][https_codeforces.com_contest_1542_proble

向右看齐/ 2022年10月12日 05:25/ 0 赞/ 211 阅读

相关 Codeforces Round #728 (Div. 2)a-c

https://codeforc.es/contest/1541 cf a b c a 给定一个数n，1 2 3 4 … n

比眉伴天荒/ 2022年10月10日 04:48/ 0 赞/ 49 阅读

相关 Codeforces Round #463 C.Permutation Cycle

一、题目 [http://codeforces.com/contest/932/problem/C][http_codeforces.com_contest_932_pr

比眉伴天荒/ 2022年05月31日 10:10/ 0 赞/ 162 阅读

相关 Codeforces Round #481 (Div. 3) C. Letters

题目链接：http://codeforces.com/contest/978/problem/C C. Letters time limit per test4 sec

àì夳堔傛蜴生んèń/ 2022年05月18日 06:19/ 0 赞/ 186 阅读

相关 Codeforces Round #118 (Div. 2) C. Plant

Dwarfs have planted a very interesting plant, which is a triangle directed "upwards". Th

蔚落/ 2022年05月17日 01:13/ 0 赞/ 233 阅读

相关 Codeforces Global Round 2（A/B/C）

这场比赛作出前两道题就挂机了，没有信心做下去了。题目链接：[http://codeforces.com/contest/1119][http_codeforces.com_

痛定思痛。/ 2022年02月22日 02:08/ 0 赞/ 133 阅读