当前位置：首页 > article >正文

平均（2023-省赛-贪心）

article 2025/1/14 15:33:40

问题描述

有一个长度为 n 的数组（n 是 10 的倍数），每个数 ai 都是区间 [0,9] 中的整数。小明发现数组里每种数出现的次数不太平均，而更改第 i 个数的代价为 bi，他想更改若干个数的值使得这 10 种数出现的次数相等（都等于 n/10），请问代价和最少为多少。

输入格式

输入的第一行包含一个正整数 n。

接下来 n 行，第 ii 行包含两个整数 ai,bi，用一个空格分隔。

输出格式

输出一行包含一个正整数表示答案。

样例输入

样例输出

样例说明

只更改第 1,2,4,5,7,8个数，需要花费代价 1+2+4+5+7+8=27。

评测用例规模与约定

对于 20% 的评测用例，n≤1000；

对于所有评测用例，n≤100000，0<bi≤200000。

注意点：

题目中说明了更改后的每个数字出现次数是n/10，而不是最后每个数字只剩下一个。

pair<first,second>的排序是先根据first来排，first相同再根据second排序。

注意题目中没有说明ai是按照从小到大的顺序输入，需要进行排序--->可以直接采用优先队列。

代码：

注意str要开辟数组，因为有很多对数字。

#include <iostream>
#include <utility>//pair
#include <algorithm>//sort
using namespace std;
pair<int,int> str[100010];
int aaa[15];
int main()
{ 
  int n;
  cin>>n;
  for(int i=1;i<=n;i++)
  {
    int a,b;
    cin>>a>>b;
    str[i].first=a;
    str[i].second=b;
    aaa[a]++;
  }
  sort(str+1,str+1+n);//默认从小到大排序
  int sum=0;
  int cnt=n/10;
  for(int i=1;i<=n;i++)
  {
    if(aaa[str[i].first]>cnt)
    {
        sum+=str[i].second;
        aaa[str[i].first]--;
    }
  }
  cout<<sum<<endl;
  return 0;
}

注意小根堆的写法。（多个优先队列构成的容器。）

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main()
{ 
  vector<priority_queue<int,vector<int>,greater<int>>> str(10);//开辟小根堆
  int n;
  cin>>n;
  for(int i=1;i<=n;i++)
  {
    int a,b;
    cin>>a>>b;
    str[a].push(b);
  }
  int sum=0;
  int cnt=n/10;
  for(int i=0;i<=9;i++)
  {
    while(str[i].size()>cnt)
    {
      sum+=str[i].top();
      str[i].pop();
    }
  }
  cout<<sum<<endl;
  return 0;
}

查看全文

http://www.kler.cn/a/502353.html