1506D Epic Transformation（思维、贪心）

ゝ一纸荒年。 2021-07-17 00:42 359阅读 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 条评论，359人围观）

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

相关阅读

相关挑战 transform() 2D

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

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

相关 [Gym-101550D] 贪心

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

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

相关思维+贪心——cf1042D

/ 首先考虑从后往前计算lis，显然0的在很多情况下的贡献要大于1 如果遇上0，那么lis++，如果遇上1，那么cnt1++，并且用cnt1更新lis

一时失言乱红尘/ 2023年10月11日 09:09/ 0 赞/ 17 阅读

相关 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 赞/ 165 阅读

相关 hdu1506

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

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

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

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

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

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

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

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

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

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

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

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

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

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

相关 1421D - Hexagons (贪心)

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

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