Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

试了所有数据,包括滑铁卢得学的出题数据,没有错,,却WA了。。

Posted by lizeliang at 2009-09-29 23:01:48 on Problem 1042
#include <iostream>
#include <queue>
#include <cstdio>
#define maxn 30
using namespace std;
int n,h;
int f[maxn],d[maxn],t[maxn],get[maxn],Time[maxn][maxn];
FILE * p;
FILE * ttt;
struct node
{
    int lakeLable;
    int fishNumber;
    node(int a,int b):
        lakeLable(a),fishNumber(b) {}
};
bool operator < (node a,node b)
{
    if(a.fishNumber == b.fishNumber)
        return a.lakeLable > b.lakeLable;
    return a.fishNumber < b.fishNumber;
}
priority_queue<node> q,temp;
bool init()
{
    if(fscanf(p,"%d",&n),!n)
        return false;
    fscanf(p,"%d",&h);
    int i;
    h*=12;
    for(i=0;i<n;i++)
        fscanf(p,"%d",&f[i]);
    for(i=0;i<n;i++)
        fscanf(p,"%d",&d[i]);
    for(i=1;i<n;i++)
        fscanf(p,"%d",&t[i]);
    t[0]=0;
    return true;
}
void solve()
{
    while(!q.empty())
        q.pop();
    memset(get,0,sizeof(get));
    memset(Time,0,sizeof(Time));
    int tt,lake,fish,i;
    for(i=0;i<n;i++)
    {
        h-=t[i];
        if(h<0)
            break;
        tt=h;
        q.push(node(i,f[i]));
        temp=q;
        while(tt && !temp.empty())
        {
            lake=temp.top().lakeLable;
            fish=temp.top().fishNumber;
            temp.pop();
            int tmp=1;
            if(!temp.empty())
            {
                if(!d[lake])
                    tmp=tt;
                else
                    tmp=(fish-temp.top().fishNumber)/d[lake];
                tmp=max(tmp,1);
                tmp=min(tmp,tt);
            }
            Time[i][lake]+=tmp;
            get[i]+=(2*fish-(tmp-1)*d[lake])*tmp/2;
            fish-=tmp*d[lake];
            tt-=tmp;
            if(fish>0)
                temp.push(node(lake,fish));
        }
        Time[i][0]+=tt;
        while(!temp.empty())
            temp.pop();
    }
    int rec=n-1;
    for(i=n-2;i>=0;i--)
        if(get[i]>get[rec])
            rec=i;
    
    fprintf(ttt,"%d",Time[rec][0]*5);
    for(int i=1;i<n;i++)
        fprintf(ttt,", %d",Time[rec][i]*5);
    fprintf(ttt,"\nNumber of fish expected: %d\n\n",get[rec]);
}
int main()
{
    char sb1[10]="G.10.dat";
    p=fopen(sb1,"r");
    ttt=fopen("a.txt","w");
    while(init())
        solve();
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator