这题个人感觉比较水。
直接贪心就OK了啊(巨贪无比)
贪心策略前面的题解说的比我清楚,我就简略说一下吧:
对花费排序,然后从小到大扫一遍
看看数量是否达到标准 超过的话就平掉
注意花费(p[i])和数量(a[i])不要搞混……
至于其他的一些问题请看代码
···cpp
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define rint register int
const int maxn=5001;
using namespace std;
inline int read(rint ans=0,rint sgn=' ',rint ch=getchar()) //读入优化,就是个板子,大家看看就好
{
for(;ch<'0' || ch>'9';sgn=ch,ch=getchar());
for(;ch>='0' && ch<='9';(ans*=10)+=ch-'0',ch=getchar());
return sgn-'-'?ans:-ans;
}
struct Node{
int p,a;
inline bool operator < (const Node &a) const { //这里是结构体排序,等价于在结构体外写个bool cmp
return p<a.p; //然而在sort函数里面因为默认使用<比较,所以定义的是<
}
}farmer[maxn];
int n,m,sum=0,ans=0,cnt=0;
int main(int argc,char **argv)
{
n=read();m=read();
for(rint i=1;i<=m;i++)
{
farmer[i].p=read();farmer[i].a=read(); //先花费,后数量!
}
sort(farmer+1,farmer+m+1); //结构体里面写完以后就是这个效果
while(sum<n) //sum是个约束条件的计数器
{
int tmp=0;cnt++;
sum+=farmer[cnt].a;
if(sum>n) tmp=sum-n,sum=n; //如果超过的话就平掉
ans+=farmer[cnt].p*(farmer[cnt].a-tmp); //保证不会超过
}
printf("%d\n",ans);
//fclose(stdin);fclose(stdout);
return 0;
}
第二种方法:快排
#include<iostream>
#include<cstdio>
using namespace std;
void sort(int,int);//快排
struct milk
{
int v;
int n;
}a[5001];
void sort(int l,int r)
{
int i,mid,j,t;
i=l;j=r;
mid=a[(l+r)/2].v;
while(i<=j)
{
while(a[i].v<mid)
{
i++;
}
while(a[j].v>mid)
{
j--;
}
if(i<=j)
{
t=a[i].v;
a[i].v=a[j].v;
a[j].v=t;
t=a[i].n;
a[i].n=a[j].n;
a[j].n=t;
i++;
j--;
}
}
if(l<j) sort(l,j);
if(i<r) sort(i,r);
}
long long wmilk;
long long ans=0;
int n;
int main()
{
scanf("%lld%d",&wmilk,&n);
int i,j,k=0;
for(i=1;i<=n;i++)
{
cin>>a[i].v>>a[i].n;
}
sort(1,n);
while(wmilk>a[k].n)
{
ans+=a[k].v*a[k].n;//装入所有
wmilk=wmilk-a[k].n;
k++;
}
ans+=wmilk*a[k].v;//装入最后的
printf("%lld",ans);
return 0;
}
第二个人的快排代码:
#include <algorithm>
//快排需要
#include <iostream>
#include <utility>
//pair所需要的头文件
#include <cstdio>
/*
标准化输入输出(scanf和printf)
不会用的同学要常常使用,这个比cin和cout快
*/
using namespace std;
int n,m;
//n是一共需要多少份牛奶,m是有多少人可以提供牛奶
//这个n也是实时更新的
pair < int , int > p[5005];//第一关键字:费用;第二关键字数量
/*
pair是STL中的一个,
有两个参数组成 ,
分别是第一关键字和第二关键字,
这里应用的原因就是:
pair 定义的数组排序按照第一关键字优先排序,
第一关键字相同按照第二关键字排序的特点
就把pair当做一个变量 first,另一个变量是second的结构体就好了,
就是在快速排序排序时可以偷懒少写一个cmp。
pair的调用也很简单,
//eg(例如)pair < int ,int > s ;(要加入分号的 )
s.first 就是第一关键字,
s.second就是第二关键字
*/
long long sum;
//不用long long可能要爆的 ,sum就是最后要输出的
int main()
{
scanf("%d%d",&n,&m);
//输入输出,记得加取地址符“&”
for(int i=0;i<m;++i)
//循环读入数据,第一关键字是单价,第二关键字是数量
scanf("%d%d",&p[i].first,&p[i].second);
sort(p,p+m);
//快排,因为用了pair所以不用写cmp排序函数
for(int i=0;i<m;++i)
//排序好了所以从头开始遍历
{
//这里的p[i]方案都是当前没有买奶的单价最便宜的
if(n<=p[i].second)
//判断如果需要买的奶<=这个奶农卖的最高数量
{
sum+=p[i].first*n;
//sum加上这个人买的单价*剩下的需要购入的牛奶
break;
//因为已经买够了,所以跳出循环
}
/*
因为如果买够了就会跳出循环,
所以这里不用在加一个if()判断了
都是在n>奶农卖的最高数量
所以当遇到这个人的时候就会买光他提供的奶
——因为贪心,
他买的是当前最便宜的,(sort排序过)
*/
sum+=p[i].first*p[i].second;
//sum加上买光这个人提供的牛奶的花费
n-=p[i].second;
/*因为我们的n是实时更新的,
所以,这个地方n要减去买入的牛奶的数量
进入下一层循环
*/
}
printf("%d\n",sum);//最后把答案输出(我个人习惯在最后输出一个换行,并不算错)
return ~~(0-0);//撒花结尾
}
第三种代码:代码最少
这题真是STL的好广告啊……用pair+sort就很方便了……
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,ans,i,t;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m;
pair<int,int> a[m];
for(;i<m;i++)cin>>a[i].first>>a[i].second;
sort(a,a+m);
for(i=0;n>0;i++)t=min(n,a[i].second),n-=t,ans+=t*a[i].first;
cout<<ans;
return 0;
}
第二个人的代码:比较短
看到这题目的时候,我也是想排序来解,后来看到农民的牛奶的单价最多是1000时候,而且每个单价都对应了一个数量,我就想用一个1000大小的数组来存放农民牛奶单价对应的牛奶数量。在求解的时候,只需要遍历一下这个数组,就能解决问题
#include <iostream>
using namespace std;
int main(){
long long n,m,ai,pi[1001]={0},sum=0;
int i,price,flag[1001]={0};
cin>>n>>m;
for(i=0;i<m;i++){
cin>>price>>ai;//农民牛奶单价和数量
pi[price]+=ai;//用相加是因为可能有相同单价的数量,不然会覆盖值
flag[price]=1;//标志这个值是有用的,存在牛奶不要钱的情况
}
for(i=0;i<=1000;i++)
if(flag[i]){
n-=pi[i];//需要数量减去农民能提供的数量
if(n>0) sum+=(i*pi[i]);//大于0则还没收购完成,可以讲当前单价的全部收购
else {n+=pi[i];sum+=(i*n);break;}//小于0或者等于0表示刚好收购够或者收多了,就得恢复原本的数量按剩余量收购
}
cout<<sum;
return 0;
}
第四种方法: 函数的运用 pair
#include<cstdio>
#include<queue>
using namespace std;
priority_queue<pair<int,int> >q;
int main(){
int n,m,ans=0,i,j;
scanf("%d%d",&n,&m);
if(n==0){
puts("0");//printf也行。纯属手懒
return 0;
}
int a,b;
for(i=1;i<=m;i++){
scanf("%d%d",&a,&b);
q.push(make_pair(-a,b));//存负权,保证取出的为实际上剩余最便宜的
}
int all=0;//all存储当前已购牛奶数量
while(1){
int k=-q.top().first;//价钱
if(all+q.top().second>=n){
ans+=(n-all)*k;//n-all为还需要牛奶数量
printf("%d",ans);
return 0;
}
all+=q.top().second;
ans+=q.top().second*k;
q.pop();
}
}
第二个人的代码:
#include<iostream>
#include<algorithm>
#include<map>
#define ll long long
#define x first
#define y second
#define INF 0x3f3f3f3f
using namespace std;
pair<ll,ll> a[2001000];
ll n,m,ans;
int main()
{
ios::sync_with_stdio(false);
cin >> m >> n;
for(int i = 1;i <= n;++i)
{
cin >> a[i].x >> a[i].y;
}
sort(a + 1,a + 1 + n);
for(int i = 1;;++i)
{
if(m > a[i].y)
{
ans += a[i].y * a[i].x;
m -= a[i].y;
}
else if(m <= a[i].y)
{
ans += m * a[i].x;
break;
}
}
cout << ans << endl;
return 0;
}
膜拜大佬