1506D Epic Transformation（思维、贪心）

ゝ一纸荒年。 2021-07-17 00:42 339阅读 0赞

[题目][Link 1]

思路：假设有只有一种数字，答案为该数字数量，两种数字，答案为大的数量减去小的数量，三种数字，假设数量从小到大排序 s1 s2 s3 ,可以知道当s1+s2<=s3, 答案为s3-(s1+s2) 当s1+s2>s3 ,如果(s1+s2+s3)%2 == 0,答案为0，(s1+s2+s3)%2 == 1，答案为1（这里好好想想应该不难，cf有一道800分的题就是只有三个数的）。然后对于数字种数为3个以上的情况，其实都可以转化为3个的情况。

Code:

#include<iostream>
    #include<map>
    #include<algorithm>
    using namespace std;
    const int Max = 1e6 + 5;
    int lst[Max];
    int main()
    { 
    	int t;cin >> t;
    	while (t--)
    	{ 
    		int n;cin >> n;
    		map<int, int> ma;
    		for (int i = 1;i <= n;i++)
    		{ 
    			int a;cin >> a;
    			ma[a]++;
    		}
    		int g = 0;
    
    		for (auto i = ma.begin();i != ma.end();i++)	lst[++g] = i->second;
    		sort(lst + 1, lst + 1 + g);
    
    		if (ma.size() == 1)	cout << ma.begin()->second << endl;
    		else if (ma.size() == 2) cout << lst[2] - lst[1] << endl;
    		else
    		{ 
    			int sum = 0;
    			for (int i = 1;i <= g - 1;i++)	sum += lst[i];
    			if (sum >= lst[g])
    			{ 
    				if ((sum + lst[g]) % 2 == 0)cout << 0 << endl;
    				else cout << 1 << endl;
    			}
    			else cout << lst[g] - sum << endl;
    		}
    	}
    }

[Link 1]: https://codeforc.es/contest/1506/problem/D

发表评论取消回复

表情：

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

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

相关阅读

相关挑战 transform() 2D

讲在先：今天只讲 2D 的部分~~~transform()transform-origin()

我会带着你远行/ 2024年05月24日 03:57/ 0 赞/ 36 阅读

相关 [Gym-101550D] 贪心

道题贪心题，硬生生的让我做成了dp 思路：低价买高价卖找非递减子序列（就是将该段序列看成多个非递减子序列的拼接） include<b...

﹏ヽ暗。殇╰゛Y/ 2024年04月17日 23:44/ 0 赞/ 43 阅读

相关 codeforces 276D 贪心

D. Little Girl and Maximum XOR time limit per test 2 seconds memory limit per test 2

妖狐艹你老母/ 2022年07月24日 06:26/ 0 赞/ 142 阅读

相关 CodeForces 825D(贪心)

问题描述: You are given two strings s and t consisting of small Latin letters, string s can

ゝ一纸荒年。/ 2022年06月06日 14:16/ 0 赞/ 114 阅读

相关 hdu1506

问题：有N条的长条状的矩形，宽度都为1，第i条高度为Hi，相邻的竖立在x轴上，求最大的子矩形面积。 ![1404154-20180709102313789-178045

快来打我*/ 2022年01月28日 10:21/ 0 赞/ 102 阅读

相关 C. Canine poetry (贪心、思维)

[题目][Link 1] 思路：首先可以知道如果我们要消灭长度>=4的回文串，那么这个大的回文串必然包含小的回文串。所以我们其实只要消灭小的回文串就可以了。其实就

谁借莪１个温暖的怀抱￠/ 2021年07月17日 01:19/ 0 赞/ 353 阅读

相关 1506D Epic Transformation（思维、贪心）

[题目][Link 1] 思路：假设有只有一种数字，答案为该数字数量，两种数字，答案为大的数量减去小的数量，三种数字，假设数量从小到大排序 s1 s2 s3 ,可以知道当

ゝ一纸荒年。/ 2021年07月17日 00:42/ 0 赞/ 340 阅读

相关 C. Basic Diplomacy （思维、贪心）

[题目][Link 1] 思路：首先为NO的情况只有，某一天只可以选一个人且某人在只可以选他的情况下被选了>⌈m2⌉次。除了这种情况，其它情况不可能为NO，看一个极端的例

谁践踏了优雅/ 2021年07月16日 23:17/ 0 赞/ 356 阅读

相关 C. Maximum width (贪心、思维)

[题目][Link 1] 思路：对于答案我们只需求取每相邻的两个元素的最大相差再从所有的最大相差取最大的即可，那么贪心一下假如要求取的是第一个和第二个元素的最大相差，那么

朴灿烈づ我的快乐病毒、/ 2021年07月16日 23:12/ 0 赞/ 345 阅读

相关 1421D - Hexagons (贪心)

[题目][Link 1] 思路：将此坐标转化为直角坐标系（纵坐标，横坐标），然后将六条路径优化，上cs = min(c6, c5 + c1), 下cx = min(c3,

清疚/ 2021年07月16日 18:45/ 0 赞/ 261 阅读