acm--4
A - A
| Time limit : 1 s | Memory limit : 32 mb |
|---|---|
| Submitted : 6 | Accepted : 2 |
| 64bit Integer Format : %lld |
|---|
Problem Description
FatMouse prepared M pounds of cat food, ready to trade with the cats guarding the warehouse containing his favorite food, JavaBean.
The warehouse has N rooms. The i-th room contains J[i] pounds of JavaBeans and requires F[i] pounds of cat food. FatMouse does not have to trade for all the JavaBeans in the room, instead, he may get J[i]* a% pounds of JavaBeans if he pays F[i]* a% pounds of cat food. Here a is a real number. Now he is assigning this homework to you: tell him the maximum amount of JavaBeans he can obtain.
The warehouse has N rooms. The i-th room contains J[i] pounds of JavaBeans and requires F[i] pounds of cat food. FatMouse does not have to trade for all the JavaBeans in the room, instead, he may get J[i]* a% pounds of JavaBeans if he pays F[i]* a% pounds of cat food. Here a is a real number. Now he is assigning this homework to you: tell him the maximum amount of JavaBeans he can obtain.
Input
The input consists of multiple test cases. Each test case begins with a line containing two non-negative integers M and N. Then N lines follow, each contains two non-negative integers J[i] and F[i] respectively. The last test case is followed by two -1's. All integers are not greater than 1000.
Output
For each test case, print in a single line a real number accurate up to 3 decimal places, which is the maximum amount of JavaBeans that FatMouse can obtain.
Sample Input
5 3 7 2 4 3 5 2 20 3 25 18 24 15 15 10 -1 -1
Sample Output
13.333 31.500
#include <stdio.h>
#include <stdlib.h>
#include <cstdio>
struct info{
double val;
int pos;
};
int amount(info a[],int n)
{
int i,j;
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
if(a[j].val>a[i].val)
{
double t;
t = a[i].val;
a[i].val=a[j].val;
a[j].val=t;
int tt;
tt=a[i].pos;
a[i].pos=a[j].pos;
a[j].pos=tt;
}
}
}
return 0;
}
int main()
{
int M,N;
int i;
while(1)
{
scanf("%d %d",&M,&N);
if(M==-1&&N==-1)
break;
info price[N]={0};
int F[N]={0},J[N]={0};
for(i=0;i<N;i++)
{
scanf("%d %d",&J[i],&F[i]);
price[i].val=(double)J[i]/F[i];
price[i].pos=i;
}
amount(price,N);
double output=0;
for(i=0;i<N;i++)
{
if(M>=F[price[i].pos])
{
output+=price[i].val*F[price[i].pos];
M-=F[price[i].pos];
}
else if(M>0&&M<F[price[i].pos])
{
output+=price[i].val*M;
M=0;
break;
}
}
printf("%.3lf\n",output);
}
return 0;
}
然而在oj里面。。。Runtime Error
没办法啊，只好看看哪里可以改进
2.sort
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
const int MAXN = 1010;
struct node
{
double j,f;
double r;
}a[MAXN];
/*
int cmp(const void *a,const void *b)//从大到小排序
{
struct node *c=(node *)a;
struct node *d=(node *)b;
if(c->r > d->r) return -1;
else return 1;
} */
bool cmp(node a,node b)
{
return a.r > b.r;
}
int main()
{
int N;
double M;
double ans;
while(scanf("%lf%d",&M,&N))
{
if(M==-1&&N==-1) break;
for(int i=0;i<N;i++)
{
scanf("%lf%lf",&a[i].j,&a[i].f);
a[i].r=(double)a[i].j/a[i].f;
}
//qsort(a,N,sizeof(a[0]),cmp);
sort(a,a+N,cmp);
ans=0;
for(int i=0;i<N;i++)
{
if(M>=a[i].f)
{
ans+=a[i].j;
M-=a[i].f;
}
else
{
ans+=(a[i].j/a[i].f)*M;
break;
}
}
printf("%.3lf\n",ans);
}
return 0;
}
key3：without sort:
#include<stdio.h>
#include<stdlib.h>
const int MAXN = 1010;
struct node
{
double j,f;
double r;
}a[MAXN];
int cmp(const void *a,const void *b)//从大到小排序
{
struct node *c=(node *)a;
struct node *d=(node *)b;
if(c->r > d->r) return -1;
else return 1;
}
int main()
{
int N;
double M;
double ans;
while(scanf("%lf%d",&M,&N))
{
if(M==-1&&N==-1) break;
for(int i=0;i<N;i++)
{
scanf("%lf%lf",&a[i].j,&a[i].f);
a[i].r=(double)a[i].j/a[i].f;
}
qsort(a,N,sizeof(a[0]),cmp);
ans=0;
for(int i=0;i<N;i++)
{
if(M>=a[i].f)
{
ans+=a[i].j;
M-=a[i].f;
}
else
{
ans+=(a[i].j/a[i].f)*M;
break;
}
}
printf("%.3lf\n",ans);
}
return 0;
}
Jack
Little Monster
Fedora 发行计时器
搜索
最新评论
日历
| 十一月 | ||||||
|---|---|---|---|---|---|---|
| 日 | 一 | 二 | 三 | 四 | 五 | 六 |
| 27 | 28 | 29 | 30 | 31 | 1 | 2 |
| 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 10 | 11 | 12 | 13 | 14 | 15 | 16 |
| 17 | 18 | 19 | 20 | 21 | 22 | 23 |
| 24 | 25 | 26 | 27 | 28 | 29 | 30 |
最新留言
功能
RSS
链接
博主寄语
来的人要留言哦！标签云
计数器
63769
2022年8月10日 12:51
GoDaddy is the largest domain registrar which brings various services to the people to bring their innovative ideas online. They sell domains that may easily searched from their search bar and does adds the services like Web / Domain Hosting, Godaddy Customer Service Number Word press Hosting, domain registration, eCommerce Solutions, Website Builder, SSL security certificates, Professional Email & Marketing, VPS, Microsoft 365 and more.