10440 - Ferry Loading II

[Zhou Yiyan@SHU]

10440 Ferry Loading II seems to be a search and optimization problem, but to my surprise, many solution only spent very little time. Is it a DP problem? I can't fnd the quick method, got TLE...and maybe WA that I don't ever know...
Could somebody give out some hint to solve the problem?

[Larry]

Use a little greed.

[Zhou Yiyan@SHU]

I still couldn't believe it has such a simple solution... though I got AC. It seems that I have to look back to my student book about greedy algorithm...

[jackie]

Consider the last n cars they should be in one ferry for the optimization time.

[vcchung]

I am not very good at programming, but I am learning.

When I try to do 10440, but I found that it has many variations so that difficult to finish it.

Can anyone please give me some ideas, guidelines or algorithm for this problem??

Many thanks!

[angga888]

I am not very good at programming, but I am learning.

When I try to do 10440, but I found that it has many variations so that difficult to finish it.

Can anyone please give me some ideas, guidelines or algorithm for this problem??

Many thanks!

think about greedy algorithm

[stcheung]

In case the hints aren't enough for the uninitiated. Basically you want to move the ferry when passenger #m (last passenger) has arrived, when passenger #(m-n) has arrived, when passenger #(m-2n) has arrived and so forth. But due to the roundtrip time, there will be some delay involved and so it boils down to calculating these delays.

[buiutripa]

anyone can help me to undertand this input/output:

in:

3
3 5 5
1 2 3 4
2 5 5
1 2 3 4
1 5 5
1 2 3 4

out:

17 2
7 1
9 1


thanks in advance!

[naseef_07cuet]

I don't know what is the problem in my code. getting WA...can anyone help me...here is my code...

Code: Select all

#include<iostream>
using namespace std;
int main()
{
    long cc,m,a[10000],i,j,k,l,mint,mintrip,c,n,t;
    cin>>c;
    for(i=0;i<c;i++)
    {
                    cin>>n>>t>>m;
                    for(j=0;j<m;j++)
                    {
                                    cin>>a[j];
                    }
                    mintrip=0;
                    int flag=0;
                    cc=0;
                    k=0;
                    for(j=0;j<m;j++)
                    {
                     if(flag!=1)
                     k=1;
                     cc=a[j];
                    if(j==0 && (m-n)>0)
                     {
                             j+=n-1;
                             cc=a[j-1];
                             mintrip++;
                             flag=0;
                             continue;
                     }
                    else if(m-(j+1)<=n && k<n && j!=0)
                     {
                               cc=a[m-1];
                               mintrip++;
                               break;
                     }
                    else if(a[j+1]-cc<=t && k<n)
                     {
                     flag=1;
                     k++;
                     continue;
                     }
                     flag=0;
                     mintrip++;
                    }
                    printf("%ld %ld\n",cc+t,mintrip);
    }
    return 0;
}

thanks in advance...

[Shafaet_du]

sample:

Code: Select all

2
2 5 5
6 
7
10
12
14
2 5 6
6 
7
10
12
14
33

Code: Select all

31 3
38 3

[zobayer]

I am getting wrong answer. I have tried a greedy approach. All the existing tests passed, I also tried many cases. I need help to fix the bug. Here is what I have come up with.

Code: Select all

AC

Thanks in advance

[EDIT]
The problem was, I didn't know that, printf evaluates it parameters right to left... like printf("%d %d\n", f(), b() ); printf first evaluates b and then f.