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,直到我用priority_queue,难道我手写的堆这么菜555555.......

Posted by roy_alice at 2012-11-09 16:51:36 on Problem 1042
还有注意两组case之间要间隔一行....其次,要是捕完鱼还有时间直接算到第一个点头上....
见代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;

struct elem
{
    int fh,num;
};
priority_queue<elem>que;
bool operator<(elem a,elem b)
{
    if(a.num==b.num) return a.fh>b.fh;
    return a.num<b.num;
}
int n,H,d[30],f[30],t[30],record[30],temp[30],ans;

void init()
{
    freopen("sin.txt","r",stdin);
    freopen("sout.txt","w",stdout);
}

void readdata()
{
    scanf("%d",&H);
    H*=12;
    int i,x;
    t[1]=0;
    for(i=1; i<=n; i++) scanf("%d",&f[i]);
    for(i=1; i<=n; i++) scanf("%d",&d[i]);
    for(i=2; i<=n; i++)
    {
        scanf("%d",&x);
        t[i]=t[i-1]+x;
    }
}

void work()
{
    memset(record,0,sizeof(record));
    int tim,i,j,opt;
    elem tem;
    ans=-1;
    for(i=1; i<=n; i++)
    {
        tim=H-t[i];
        if(tim<=0) break;
        while(!que.empty()) que.pop();
        for(j=1; j<=i; j++)
        {
            tem.fh=j;
            tem.num=f[j];
            que.push(tem);
        }
        opt=0;
        memset(temp,0,sizeof(temp));
        while(tim)
        {
            tem=que.top();
            que.pop();
            if(tem.num<=0)
            {
                temp[1]+=tim;
                break;
            }
            opt+=tem.num;
            temp[tem.fh]++;
            tem.num-=d[tem.fh];
            que.push(tem);
            //downmodify(1);
            tim--;
        }
        if(opt>ans)
        {
            for(j=1; j<=i; j++) record[j]=temp[j];
            ans=opt;
        }
    }
    for(i=1; i<n; i++) printf("%d, ",record[i]*5);
    printf("%d\n",record[n]*5);
    printf("Number of fish expected: %d\n\n",ans);
}

int main()
{
    //init();
    while(1)
    {
        scanf("%d",&n);
        if(n==0) break;
        readdata();
        work();
    }
    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