暑假热身 B. 下载测速

最近，nono终于结束了每年一次的为期12个月的冬眠，醒来的第一件事就是——看电影！！nono发现最近一年出现了各种很好很强大的电影，例如这个、这个、还有这个。

于是nono直接把这些电影全部扔进了下载列表之中。已知nono下载了N部电影，其中第i部电影的大小为Si，该电影最大下载速度不会超过Vi，在任一时刻全部电影的下载速度之和不会超过Vt。现在nono希望知道在这些条件下至少需要多长时间才能将这些电影全部下完。

Input

多组输入。每组输入的第一行为两个整数N,Vt(0<N≤10⁶, 0<Vt≤10⁹)。接下来的N行每行两个整数表示Si, Vi(0<Si,Vi≤1000)。输入以EOF结束。

Output

对于每组数据，输出一个既约分数表示下载完全部电影所需的最少时间。

Sample Input

Sample Output

5/2
3/1

这道题一开始想复杂了，所有任务同时开始同时结束即可、比较单个任务的最长时间。

第一个版本测试的所有数据都没有问题，不知道哪里出的错总是WA

#include<stdio.h>
struct DongSer
{
    int a;
    int b;
};
struct DongSer d;
int da,db;
void sim(int i,int j)
{
    int k=i-1;
    if(i==j){i=j=1;}
    if(i%j==0){i=i/j;j=1;da=i;db=j;return;}
    if(j%i==0){j=j/i;i=1;da=i;db=j;return;}
    while(1)
    {
        if(k==1){da=i;db=j;return;}
        if(i%k==0&&j%k==0){i=i/k;j=j/k;}
        else {k--;}
    }
}

int main()
{
    int i,j,k,n,vt;
    double m,t,p;
    while(scanf("%d%d",&n,&vt)!=EOF)
    {
        for(i=1;i<=n;i++)
        {
            scanf("%d%d",&d.a,&d.b);
            j+=d.a;
            t=d.a/d.b;
            if(t>p){p=t;k=i;da=d.a;db=d.b;}
        }
        m=j/vt;
        if(m>=p){da=j;db=vt;sim(da,db);printf("%d/%d
",da,db);}
        if(m<p){sim(da,db);printf("%d/%d
",da,db);}
        i=j=k=n=vt=m=t=p=da=db=d.a=d.b=0;
    }
    return 0;
}

View Code


AC版本：

#include <iostream>
#include <cstdio>
using namespace std;
int n, vt;
int gcd (int a, int b)
{ while (b != 0)
{ int t; a %= b; t = a; a = b; b = t; }
return a;
}
int main ()
 { ios::sync_with_stdio(false);
 while (cin >> n >> vt)
    { int sum = 0; int rs = 0, rv = 1;
 for (int i = 0; i < n; ++i)
    { int s, v;
 cin >> s >> v; sum += s; if ((double)rs/rv < (double)s/v) { rs = s; rv = v; } } if ((double)rs/rv < (double)sum/vt) { rs = sum; rv = vt; } int k = gcd(rs, rv); cout << rs/k << "/" << rv/k << endl; } return 0; }

View Code