JZOJ.1150【贪心算法】IQ
2024-09-04 22:14:22
欢迎转载,请附上原链接https://www.cnblogs.com/Code-Garden/p/11276741.html(也没人会看)
一道对我来说较难的贪心题
题目描述
根据世界某权威学会的一项调查,学信息学的学生IQ非常高。举个最好的例子,如果我们把学信息学的一些学生调去学数学,那么两个竞赛的学生平均IQ都会提升!!
现在给出一群数学竞赛全体学生的IQ和信息学竞赛全体学生的IQ,问最多能把几个学信息学的学生调去学数学,而两个竞赛的学生平均IQ都有提升呢?
每次只调一个学生,而且每次调配,两个竞赛的学生平均IQ都要提升。
输入
第1行一个正整数N(N≤I00),代表数学竞赛班学生的数目;
第2行,有N个正整数,代表每个数学学生的IQ(1到200之间);
第3行,一个整数M(M≤100),代表信息学竞赛班学生数目;
第4行,有M个正整数,代表每个信息学竞赛班学生的IQ(1到200之间)。
输入数据保证信息学学生平均IQ高于数学学生。
输出
一个正整数,代表能从信息学调去学数学的学生的个数。
样例输入
3
3 2 3
3
3 2 5
样例输出
1
这题有n个坑,一开始我以为题目让我将数学和信息学的学生对调。
贪心思路:
- 排序信息学IQ
2.一个个模拟。(暴力)
不说了,放代码。
#include<bits/stdc++.h>
using namespace std;
int n,m,suma,sumb,hi,ans,ts;
int a[101],b[101],h[101];
double pa,pb;
int cmp(const int &a,const int &b)
{
return a<b;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
suma+=a[i];
}
cin>>m;
for(int i=1;i<=m;i++)
{
cin>>b[i];
sumb+=b[i];
}
pa=suma*1.0/n; //平均IQ
pb=sumb*1.0/m;
sort(b+1,b+m+1,cmp); //STL用得爽,一直用就一直爽
int mm=m;
for(int i=1;i<=mm;i++) //逐个模拟
{
if(b[i] > pa && b[i] < pb)
{
ans++; //乱搞一通
suma+=b[i];
sumb-=b[i];
m--,n++;
pa=suma*1.0/n;
pb=sumb*1.0/m;
}
}
cout<<ans<<endl;
return 0;
}
|| 素质三连走起
v
最新文章
- 相克军_Oracle体系_随堂笔记005-Database buffer cache
- C#网络编程之---TCP协议的同步通信(二)
- 关于conky
- 打包时Xcode报:此证书的签发者无效Missing iOS Distribution signing identity
- BZOJ4196 软件包管理器
- HDU 2159 FATE(二维费用背包)
- mysql 特殊语句
- 上一篇下一篇 排序 (非ID字段排序)
- Java filter拦截器的使用
- visual studio 2012打开提示 未能将网站&#215;&#215;&#215;配置为使用 ASP.NET 4.5 和 尚未在Web服务器上注册,您需要手动将Web服务器配置为使用ASP.NET 4.5
- 使用JsonProperty Attribute修改返回json
- opensips redis配置记录
- Servlet案例2:文件下载
- enumerate()用法
- 转:C#串口编程
- oninput和onpropertychange实时监听输入框值的变化
- POJ 1166 暴力搜索 即 枚举
- yum 安装指定 kernel 版本源码
- BZOJ2831(小强的金字塔系列问题--区域整点数求法)
- zipkin:和springcloud集成过程记录