Sort by T1.
Then set timer=0,  ans =0.
Then for all students in sorted order:
if timer<T1 then timer=T1
timer=timer+T2
dtime=timer-T3
if dtime>ans then ans=dtime

What happens if 2 or more student are ready at one at the same time(they have equal T1)? Who will be first in queue?

var
 t1,t2,t3:array[0..50] of longint;
procedure qsort(l,r:longint);
var i,j,x,put:longint;
begin
 i:=l;j:=r;x:=t1[(i+j) shr 1];
 repeat
  while x>t1[i] do inc(i);
  while x<t1[j] do dec(j);
  if i<=j then
   begin
    put:=t1[i];t1[i]:=t1[j];t1[j]:=put;
    put:=t2[i];t2[i]:=t2[j];t2[j]:=put;
    put:=t3[i];t3[i]:=t3[j];t3[j]:=put;
    inc(i);dec(j);
   end;
 until i>j;
 if i<r then qsort(i,r);
 if j>l then qsort(l,j);
end;

var
 n,i,temp,need:longint;
begin
 readln(n);
 for i:=1 to n do
  readln(t1[i],t2[i],t3[i]);
 qsort(1,n);
 for i:=1 to n do
  begin
   t1[i]:=t1[i]-temp;
   if t1[i]<0 then t1[i]:=0;
   temp:=temp+t1[i]+t2[i];
   if t3[i]<temp then need:=need+(temp-t3[i]);
  end;
 writeln(need);
end.




Wrong Answer TEST 10.

Test my code, please.


#include <iostream>
#include <string>
#include <vector>
#include <queue>
using namespace std;

int N;

bool proverka(vector <int> &used, queue <int> &Q){
    if (!Q.empty()) return true;
    for (int i=0;i<N;i++)
        if (!used[i]) return true;
    return false;
}

int main(){
    cin>>N;
    vector <int> T1(N);
    vector <int> T2(N);
    vector <int> T3(N);
    for (int i=0;i<N;i++)
        cin>>T1[i]>>T2[i]>>T3[i];
    vector <int> used(N,0);
    queue <int> Q;
    int res=0;
    int tres=0;
    for (int m=0;m<4*N;m++){
        int t=-1;
        for (int i=0;i<N;i++)
            if (!used[i] && (t==-1 || T1[i]<T1[t]))
                t=i;

        //cout<<t+1<<": "<<T1[t]<<" "<<T2[t]<<" "<<T3[t]<<" "<<Q.front()<<endl;
        if (Q.empty() && t==-1)
            continue;

        if (Q.empty()){
            res+=T1[t];
            used[t]=1;
            Q.push(t);
            for (int i=0;i<N;i++)
                if(!used[i]){
                    T1[i]-=T1[t];
                    if (T1[i]<=0){
                        Q.push(i);
                        used[i]=1;
                    }
                }
            continue;
        }

        if (t==-1){
            res+=T2[Q.front()];
            tres=max(tres,(res-T3[Q.front()]<0 ? 0 : res-T3[Q.front()]));
            Q.pop();
            continue;
        }

        if (T1[t]<T2[Q.front()]){
            res+=T1[t];
            used[t]=1;
            Q.push(t);
            for (int i=0;i<N;i++)
                if(!used[i]){
                    T1[i]-=T1[t];
                    if (T1[i]<=0){
                        Q.push(i);
                        used[1]=1;
                    }
                }
            T2[Q.front()]-=T1[t];
            if (T2[Q.front()]<=0)
                Q.pop();
            continue;
        }

        if (T1[t]>T2[Q.front()]){
            res+=T2[Q.front()];
            tres=max(tres,(res-T3[Q.front()]<0 ? 0 : res-T3[Q.front()]));
            for (int i=0;i<N;i++)
                if (!used[i]){
                    T1[i]-=T2[Q.front()];
                    if (T1[i]<=0){
                        Q.push(i);
                        used[1]=1;
                    }
                }
            Q.pop();
            continue;
        }

    }

    cout<<tres<<endl;
    return 0;
}

input:
3
100 100 100
101 100 100
102 100 100

out:
300

I forgot to update each T1 with the shift time and got WA#10.
Interestingly, code with such big bug passes the 1~9 test case.

import java.util.Scanner;

public class Queue {

    public static void main(String[] args) {

        Scanner input = new Scanner(System.in);
        koor A[] = new koor[50];
        int i, j, st;
        int vaxt = 0;
        int temp, temp1, temp2;
        int max = 0;
        int N = input.nextInt();

        for (i = 1; i <= N; i++) {
            A[i] = new koor();
            A[i].T1 = input.nextInt();
            A[i].T2 = input.nextInt();
            A[i].T3 = input.nextInt();
        }


        for (i = 1; i <= N - 1; i++) {

            for (j = 1; j <= N - 1; j++) {

                if (A[j].T1 > A[j + 1].T1) {

                    temp = A[j].T1;
                    A[j].T1 = A[j + 1].T1;
                    A[j + 1].T1 = temp;

                    temp1 = A[j].T2;
                    A[j].T2 = A[j + 1].T2;
                    A[j + 1].T2 = temp1;

                    temp2 = A[j].T3;
                    A[j].T3 = A[j + 1].T3;
                    A[j + 1].T3 = temp2;

                }
            }
        }


        st = A[1].T1 + A[1].T2;

        if (st > A[1].T3) {
            vaxt = st - A[1].T3;
        }
        for (i = 2; i <= N; i++) {

            if (st > A[i].T1) {
                st += A[i].T2;
                if (st > A[i].T3) {
                    vaxt = st - A[i].T3;
                }
            } else {
                st = A[i].T1 + A[i].T2;
                if (st > A[i].T3) {
                    vaxt = st - A[i].T3;
                }
            }
            if (vaxt > max) {
                max = vaxt;
            }

        }
        System.out.println(max);
    }
}

class koor {

    int T1;
    int T2;
    int T3;
}

Edited by author 30.05.2010 15:45

program Project2;
{$APPTYPE CONSOLE}
uses
  SysUtils;
type
  tt = record
    t1, t2, t3: integer;
  end;
var
  i, n, time, tek: integer;
  a: array[1..50] of tt;
begin
  readln(n);
  for i := 1 to n do
    readln(a[i].t1, a[i].t2, a[i].t3);

{  sort(1, n);}
//....a[1].t1<a[2].t1<.....<a[n].t1
  time := 0;
  tek := 0;
  for i := 1 to n do
  begin
    if tek >= a[i].t1 then
      tek := tek + a[i].t2
    else
      tek := a[i].t1 + a[i].t2;
    if tek > a[i].t3 then
    begin
      time :=time+ tek - a[i].t3;
      tek := a[i].t3;
    end
  end;
  writeln(time);
end.

This is my program:
#include <stdio.h>

int main ()
{
    int n;
    int mas[100][3] = {};
    bool maska[100] = {};
    int solution = 0;
    int sum = 0;
    int min = 601, k = 0;
    scanf ("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf ("%d%d%d", &mas[i][0], &mas[i][1], &mas[i][2]);
        if (mas[i][0] < min)
        {
            min = mas[i][0];
            k = i;
        }
    }
    sum = mas[k][0];
    maska[k] = 1;
    bool ok = false;
    int exit = 0;
    int save_i = 0;
    while (ok == false)
    {
        min = 9999999;
        sum += mas[k][1];
        maska[k] = 1;
        ok = true;
        if (sum > mas[k][2]) solution += sum - mas[k][2];
        bool key = false;
        exit = k;
        if (k == n - 1) k = -1;
        for (int i = k + 1; i < n; i++)
        {
            if (exit == i) break;
            if (maska[i] == 1) ok = true;
            if ((maska[i] == 0) && (mas[i][0] > sum) && (mas[i][0] < min))
            {
                min = mas[i][0];
                save_i = i;
                key = true;
            }
            if ((maska[i] == 0) && (mas[i][0] <= sum))
            {
                k = i;
                ok = false;
                break;
            }
            if (i == n - 1) i = -1;
        }
        if ((ok == true) && (key == true))
        {
            ok = false;
            k = save_i;
            sum = mas[k][0];
        }
    }
    printf ("%d", solution);

    return 0;
}

I'm sorry, but WTF???
My program works correct on sample and all other tests, but I got WA1 ><
Code:

program abcdefgh;

var t1,t2,t3: array[1..100] of longint;
i,k,j,n,time: longint;

begin
read(n);
for i:=1 to n do
 readln(t1[i],t2[i],t3[i]);
for i:=1 to n-1 do
for j:=i+1 to n do begin
 if t1[i]>t1[j] then begin
                     k:=t1[i]; t1[i]:=t1[j]; t1[j]:=k;
                     k:=t2[i]; t2[i]:=t2[j]; t2[j]:=k;
                     end;
 if t3[i]>t3[j] then begin
                     k:=t3[i]; t3[i]:=t3[j]; t3[j]:=k;
                     end;
end;
time:=0;
for i:=1 to n do
 if t1[i]<time then inc(time,t2[i]) else
                    time:=t1[i]+t2[i];
if time-t3[1]<0 then writeln(0) else writeln(time-t3[1]);
end.

Edited by author 25.06.2009 16:17

Crash, because in Input numbers t1, t2, t3 separeted more then one space.
So, I replaced
string[] ss = Console.ReadLine().Split(' ');
to
string[] ss = Console.ReadLine().Split(new char[]{' '},StringSplitOptions.RemoveEmptyEntries);
and got AC.

I try many tests but not find out any mistake in my program ! Why ?

Edited by author 13.02.2009 08:52

Edited by author 13.02.2009 08:52

This is my code:

var n,i,j,max,k:integer;
t1,t2,t3:array[1..101] of integer;
begin
read(n);
k:=0;
for i:=1 to n do read(t1[i],t2[i],t3[i]);
for i:=1 to n do
for j:=n downto i+1 do
if t1[i]>t1[j] then
begin
k:=t1[i];
t1[i]:=t1[j];
t1[j]:=k;
k:=t2[i];
t2[i]:=t2[j];
t2[j]:=k;
k:=t3[i];
t3[i]:=t3[j];
t3[j]:=k;
end;
k:=t1[1];
max:=0;
j:=0;
for i:=1 to n do
begin
inc(k,t2[i]);
if k>t3[i] then j:=k-t3[i];
if j>max then max:=j;
end;
write(max);
end.

Sorry for Russian...
Помогите мне пожалуйста, буду очень благодарен!!!

Edited by author 28.08.2008 23:40

What's wrong?

#include <stdio.h>
#include <stdlib.h>
int n,x,s;
typedef struct{
        int t1,t2,t3;
}st;
st t[110];
int max(int a,int b){
if(a>b)return a;
else return b;
}
int cmp(const void *a,const void *b){
        const st *c=(st *)a, *d=(st *)b;
        return c->t1 - d->t1;
}
int main(){
        scanf("%d",&n);
        for(int i=0;i<n;i++){
                scanf("%d %d %d",&t[i].t1,&t[i].t2,&t[i].t3);
        }
        qsort(t,n,sizeof(st),cmp);
        for(int i=0;i<n;i++){
                t[i].t1=max(t[i].t1,x);
                x=t[i].t1 + t[i].t2;
                s+=max(0,x-t[i].t3);
        }
        printf("%d\n",s);
return 0;
}

I am still getting WA#8. Please, give ne some hints or tests.

#include <stdio.h>

int main()
{
 struct student {
 long t1;
 long t2;
 long t3;
 };

 student stu[100];
 long max=0,stm=0;
 int i,j,n,tmp;

 scanf("%d",&n);

 for(i=0;i<n;i++) { stu[i].t1=0;stu[i].t2=0;stu[i].t3=0; }
 for(i=0;i<n;i++) scanf("%d %d %d",&stu[i].t1,&stu[i].t2,&stu[i].t3);

  for (i=0; i<n; i++) {
  for (j=0; j<n-1; j++)
    if (stu[j+1].t1 < stu[j].t1) {
      tmp = stu[j].t1;
      stu[j].t1 = stu[j+1].t1;
      stu[j+1].t1 = tmp;

      tmp = stu[j].t2;
      stu[j].t2 = stu[j+1].t2;
      stu[j+1].t2 = tmp;

      tmp = stu[j].t3;
      stu[j].t3 = stu[j+1].t3;
      stu[j+1].t3 = tmp;
  }
 }

 stm=stu[0].t1;

 for(i=0;i<n;i++) {
    stm=stm+stu[i].t2;
    j=stm-stu[i].t3;
    if(j>max)max=j;
 }

 printf("%d",max);

 return 0;
}

My algorithm is
1. sort wait time min -> max
2. variable time declared to add total time
3. add minimal wait time and exam time to var(time)
4. add exam time everybody
5. if time > freetime print time-freetime
   else print 0
I think my algorithm is right ,but I got WA #7
Could you help me plz?

这道题用中文怎么解释？