AcWing 5395. 平均
原题链接
中等
作者:
House12
,
2024-01-10 13:31:48
,
所有人可见
,
阅读 56
题目类型:贪心
思路
尽量把代价多的不做更改,剩余代价小的依次做更改
代码步骤:
1.排序,把代价从小到大排序
2.把要更改的数从代价小的开始更改
正解代码
#include<bits/stdc++.h> //万能头文件
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int N=1e5+5,M=10;
PII nums[N]; //用来记录每一个数字和这个数字的价值
vector<int> cost[M];
int n;
int main()
{
cin>>n;
for(int i=0;i<n;i++)
cin>>nums[i].first>>nums[i].second;
sort(nums,nums+n); //按每个数字所需要的代价从小到大排序
for(int i=0;i<n;i++)
cost[nums[i].first].push_back(nums[i].second);
int t=n/10; //每个数字应该出现的次数
LL res=0;
for(int i=0;i<10;i++)
{
int x=cost[i].size();
if(x>t) //对出现超过t次的数字进行更改
{
for(int j=0;j<x-t;j++)
res+=cost[i][j];
}
}
cout<<res; //输出最少的代价和
return 0; //好习惯
}