F. Equalize the Array (map、思维)

た入场券 2021-07-16 13:38 377阅读 0赞

[题目][Link 1]

思路：  
看一个例子  
x:y 表示 拥有x个相同的数有y个(2:3 1 1 2 2 3 3)

现在有 4:5 3:3 1:8 即 有5个数量为4的数 3个数量为3的数 8个数量为1的数

现在我们要求使得剩下的数的数量都相同的最少删去数的个数，即让剩下数的个数最大

我们假设要让最后所有的数都剩下数量为4，那么把1和3的所有数删掉即可，剩下数的个数4\*5=20.

继续这个过程如要让剩下的数数量都为3，那么我们需将那5个数量为4的数各自删掉一个数，再加上所有数量为3的数，即为20-（4-3）\*5+3 \* 3=24，此时有3+5个数量为3的数

再继续，让剩下的数的个数都为1，需将8个数量为3的数都相减2再加上8个数量为1的数 24-(3-1)\*8+1 \*8=16.  
最终答案取20 24 16 所有情况的最大值24

Code:

#include<iostream>
    #include<map>
    using namespace std;
    typedef long long ll;
    const int Max = 1e6 + 5;
    int Mod = 1e9 + 7;
    ll lst[Max];
    
    int main()
    { 
    	int t;cin >> t;
    	while (t--)
    	{ 
    		map<ll, ll,greater<ll>> ma1, ma2;
    		int n;cin >> n;
    		for (int i = 1;i <= n;i++) {  cin >> lst[i];ma1[lst[i]]++; }
    		for (auto i = ma1.begin();i != ma1.end();i++)ma2[i->second]++;
    		ll sum = ma2.begin()->first * ma2.begin()->second;
    		ll ma = sum;auto j = ma2.begin();
    		for (auto i = ++ma2.begin();i != ma2.end();i++)
    		{ 
    			sum += i->first * i->second;
    			sum -= (j->first - i->first) * j->second;
    			i->second += j->second;
    			ma = max(ma, sum);
    			j = i;
    		}
    		cout << n - ma << endl;
    	}
    }

[Link 1]: https://codeforc.es/problemset/problem/1490/F

发表评论取消回复

表情：

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

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

相关阅读

相关 LeetCode（Array)1470. Shuffle the Array

1.问题 Given the array nums consisting of 2n elements in the form \[x1,x2,…,xn,y1,y2,…,

叁歲伎倆/ 2023年09月23日 22:55/ 0 赞/ 46 阅读

相关 F4map

F4是法国一家专长于3D显示技术的科技公司。其面向公众的地图产品F4map，基于WebGL技术和OpenStreetMap的基础数据的完美组合，展现出一个十分炫酷的3D场景。

喜欢ヅ旅行/ 2022年07月12日 14:54/ 0 赞/ 73 阅读

相关 Array.prototype.map()

map() 方法创建一个新数组，其结果是该数组中的每个元素调用一个提供的函数。参数 callback：生成新数组元素的函数，使用三个参数： curr

红太狼/ 2022年06月18日 00:57/ 0 赞/ 124 阅读

相关 js array map()

var array1=Array(3); array1[0]=2; var result=array1.map(element=>'1');

系统管理员/ 2022年05月30日 08:20/ 0 赞/ 149 阅读

相关 Function-Array map()

定义和用法 array.map(function(currentValue,index,arr), thisValue) map() 方法返回一个新数组，数组中

骑猪看日落/ 2022年03月30日 17:14/ 0 赞/ 202 阅读

相关 F - Minimum Sum of Array

You are given an array a consisting of n integers a1, ..., an. In one operation, you can

傷城~/ 2022年03月19日 15:22/ 0 赞/ 134 阅读

相关 array_reduce() 与 array_map()

相似部分：　　二者同为处理数组函数，可遍历数组中的每一个元素，对其通过 function callback()\{\} 处理。不同处

柔情只为你懂/ 2021年10月25日 13:42/ 0 赞/ 311 阅读

相关 D. A Leapfrog in the Array （思维）

[题目][Link 1] 思路：经过模拟可以发现对于一个元素的移动每次移动量是之前一次的两倍，如果将列表倒过来从0开始，那么每次元素的位置移动便是x=2x+1，现在给出了

冷不防/ 2021年07月16日 21:55/ 0 赞/ 348 阅读

相关 C. Two Arrays (dp、思维)

[题目][Link 1] a\[i\]\[j\] 表示前i个数字中第i个数字为j的所有情况的非递减序列的数目 b\[i\]\[j\] 表示前i个数字中第i个数字为j

浅浅的花香味﹌/ 2021年07月16日 19:19/ 0 赞/ 440 阅读

相关 F. Equalize the Array (map、思维)

[题目][Link 1] 思路：看一个例子 x:y 表示拥有x个相同的数有y个(2:3 1 1 2 2 3 3) 现在有 4:5 3:3 1:8 即

た入场券/ 2021年07月16日 13:38/ 0 赞/ 378 阅读