Jack's Blog

流淌的心,怎能阻拦,吹来的风,又怎能阻挡。

acm--4

Jacob posted @ Sep 18, 2017 08:28:28 PM in C语言 with tags C语言 acm , 641 阅读

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.
 

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;
}
Avatar_small
Godaddy Customer Ser 说:
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.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter