Time limit : 1 s | Memory limit : 32 mb |
---|---|
Submitted : 6 | Accepted : 2 |
64bit Integer Format : %lld |
---|
#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; }
二月 | ||||||
---|---|---|---|---|---|---|
日 | 一 | 二 | 三 | 四 | 五 | 六 |
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 | 1 | 2 |