Editorial for Xe ô tô của bò


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của RR

{$R-,Q-}
//super fast algorithm invented by mr_invincible
const
  FINP='';
  FOUT='';
  MAXN=50000;
var
  n,l,m,d,kq:longint;
  a:array[1..MAXN] of longint;
procedure inp; inline;
var
  f:text;
  i:longint;
begin
  assign(f,FINP); reset(f);
  read(f,n,m,d,l);
  for i:=1 to n do read(f,a[i]);
  close(f);
end;
procedure swap(var a,b:longint); inline;
var
  temp:longint;
begin
  temp:=a; a:=b; b:=temp;
end;
procedure sort(l,r:longint); inline;
var
  i,j,mid:longint;
begin
  i:=l; j:=r; mid:=a[l+random(r-l+1)];
  repeat
    while a[i]<mid do inc(i);
    while a[j]>mid do dec(j);
    if i<=j then
      begin
        swap(a[i],a[j]);
        inc(i); dec(j);
      end;
  until i>j;
  if i<r then sort(i,r);
  if l<j then sort(l,j);
end;
procedure ans; inline;
var
  f:text;
  i:longint;
begin
  assign(f,FOUT); rewrite(f);
  kq:=0;
  for i:=1 to n do
    if a[i]-d*(kq div m)>=l then inc(kq);
  writeln(f,kq);
  close(f);
end;
begin
  inp;
  sort(1,n);
  ans;
end.

Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>
long min(long a,long b)
  {
  if(a<b) return a;
  else return b;
  }
void quickSort(long A[],long lower,long upper)
{
        long x = A[(lower + upper) / 2];
        long i = lower;
        long j = upper;
        do{
                while(A[i] > x)
                        i ++;
                while (A[j] < x)
                        j --;
                if (i <= j)
                {
                     long tg=A[i];
                     A[i]=A[j];
                     A[j]=tg;   
                        i ++;
                        j --;
                }
        }while(i <= j);
        if (j > lower)
                quickSort(A, lower, j);
        if (i < upper)
                quickSort(A, i, upper);
}
main()
{
long n,m,d,l,s[50001],a[50001],b[50001],C[50001],KQ;
scanf("%ld %ld %ld %ld",&n,&m,&d,&l);
for(long i=1;i<=n;i++)
  {         
  scanf("%ld",&s[i]);
  if(d>0)
    {
    if(s[i]<l)
      a[i]=-1;
    else        
      a[i]=(s[i]-l)/d;
    }
  else
    {
    if(s[i]>=l)
      a[i]=1000000;
    else a[i]=-1;
    }    
  }
KQ=n;  
quickSort(a,1,n);
for(long i=1;i<=m;i++)
  C[i]=1000000;
for(long i=1;i<=n;i++)
  {
  //printf("%ld ",a[i]);       
  C[(i-1)%m+1]=min(C[(i-1)%m+1]-1,a[i]);  
  if(C[(i-1)%m+1]<0)
    {
    KQ=i-1;
    break;
    }
  }
printf("%ld",KQ);
//getch();
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.