[Offer收割]编程练习赛46 register

Ended

Participants:142

Verdict:Accepted
Score:100 / 100
Submitted:2018-01-28 14:06:11

Lang:G++

Edit
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
31
#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;
ll n,k,p[1005];
ll check(ll x,int idx){
    ll sum=0;
    for(int i=0;i<n;++i){
        ll tot=x*p[i]/p[idx];
        sum+=tot;
    }
    return sum;
}
int main(void){
    scanf("%lld%lld",&n,&k);
    for(int i=0;i<n;++i)
        scanf("%lld",&p[i]);
    ll l,r,mid;
    for(int i=0;i<n;++i){
        l=1;r=p[i]-1;
        while(l<r){
            mid=(l+r)/2;
            if(check(mid,i)>=k)r=mid;//>=
            else l=mid+1;
        }
        if(check(r,i)==k){
            printf("%lld/%lld\n",r,p[i]);
            break;
        }
    }
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX