MINROAD spoj VOI2014 - Con duong Tung Truc

Nguồn đề bài http://vn.spoj.com/problems/MINROAD/

1. Đề bài MINROAD spoj

Địa điểm du lịch Dailai nổi tiếng với con đường Tùng-Trúc. Đó là một con đường dài và thẳng, dọc bên đường người ta trồng rất nhiều cây tùng và cây trúc. Với mục đích tạo điểm nhấn cho con đường, Ban quản lý khu du lịch muốn chọn một đoạn đường mà dọc theo nó có ít nhất a cây tùng và có ít nhất b cây trúc để trang trí. Sau khi khảo sát, Ban quản lý ghi nhận được vị trí của từng cây tùng và cây trúc. Trên con đường có tất cả n cây, không có hai cây nào ở cùng một vị trí. Cây thứ i ở ị trí có khoảng cách đến vị trí bắt đầu của con đường là d_i (i = 1, 2, …, n). Với kinh phí có hạn, Ban quản lý muốn chọn một đoạn đường thỏa mãn điều kiện đã nêu với độ dài là ngắn nhất.

Yêu cầu

Cho a, b và vị trí của n cây. Hãy tìm đoạn đường có độ dài ngắn nhất mà dọc theo đoạn đường đó có ít nhất a cây tùng và b cây trúc.

Input

Dòng đầu chứa 3 số nguyên dương n, a, b (a + b <= n)
Dòng thứ i trong n dòng tiếp theo mỗi dòng chứa hai số nguyên dương d_i (d_i <= 10^9) trong đó d_i là khoảng cách của cây tính từ vị trí bắt đầu của con đường, k_i = 1 nếu cây thứ i là cây tùng, k_i = 2 nếu là cây trúc.
Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.

Output

Ghi ra một số nguyên là độ dài đoạn đường ngắn nhất tìm được, quy ước ghi số -1 nếu không tồn tại đoạn đường nào thỏa mãn điều kiện đặt ra.

Giới hạn

d_i <= 10^9.
30% số test có n <= 300.
30% số test khác có n <= 3000.
40 % số test còn lại có n <= 300000.

Example

Input:
7 2 2
20 2
30 1
25 1
35 1
60 2
65 2
10 1

Output:
35

2. Lời giải MINROAD spoj

a. Lời giải 1

(LỜI GIẢI: Nguyễn Duy Khánh)

Ta lưu 2*n điểm vào mảng T:

T[i].d là khoảng cách đến vị trí bắt đầu của con đường
T[i].k là 1 nếu là cây tùng, là 2 nếu là cây trúc

Sắp xếp mảng T theo thứ tự tăng dần T[i].d

Với mỗi T[i], ta phải tìm vị trí X sao cho từ T[i] đến T[x] có ít nhất a cây tùng và b cây trúc. Đặt F[i]=X.

Dễ dàng nhận thấy: F[i] <= F[i+1] nên ta có thể sử dụng 2 vòng For để tính toán kết quả như sau:

For i=1 to 2*N do

For j=F[i-1] to 2*N do ……..

Thay vì dùng mảng F, bạn hoàn toàn có thể sử dụng biến chạy mà thôi

Code tham khảo MINROAD spoj c++

Độ phức tạp: O(N log N)

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
typedef pair<int,int> ii;

int main()
{
    //freopen("test.inp.c","r",stdin);
    int n,i,j,k,a,b,s[2]={0};
    vector<ii> v;
    scanf("%d%d%d",&n,&a,&b);
    for(i=0;i<n;++i)
    {
        scanf("%d%d",&j,&k);
        v.push_back(ii(j,k));
    }
    sort(v.begin(),v.end());
    j=-1;k=1e9;
    for(i=0;i<n;++i)
    {
        if(i) --s[(v[i-1].second)&1];
        while((s[1]<a || s[0]<b) && j<n) ++s[(v[++j].second)&1];
        if(j==n) break;
        k=min(k,v[j].first-v[i].first);
    }
    if(k==1e9) printf("-1");
    else printf("%d",k);
}

b. Lời giải 2

cũng sắp xếp như ý tưởng đầu tiên

Xây dựng mảng đếm số cây tùng và số cây trúc từ đầu đến vị trí i. o(n).

ý tưởng: chỉ cần duyệt bắt đầu từ vị trí đã thỏa điều kiện. khi tìm tìm thấy vị trí khác cho kết quả tốt hơn thì lần sau bắt đầu duyệt từ đó. và tất nhiên khi chưa tìm thấy gì hết thì phải duyệt tìm từ vị trí đầu tiên.

Code tham khảo MINROAD spoj pascal

const   fi='';
        nmax=300100;
type    data=longint;
var
        f:text;
        D:array[0..nmax] of data;
        id:array[0..nmax] of byte;
        n,a,b:data;
        suma,sumb,vt:array[0..nmax+1] of data;

procedure docfile;
var     i,j:data;
begin
        assign(f,fi); reset(f);
        readln(f,n,a,b);
        for i:=1 to n do
                readln(f,d[i],id[i]);
        close(f);
end;


procedure sort(l,r: longint);
      var
         i,j,x,y: longint;
         z:byte;
      begin
         i:=l;
         j:=r;
         x:=d[(l+r) shr 1];
         repeat
           while d[i]<x do
            inc(i);
           while x<d[j] do
            dec(j);
           if not(i>j) then
             begin
                y:=d[i];
                d[i]:=d[j];
                d[j]:=y;

                z:=id[i];
                id[i]:=id[j];
                id[j]:=z;
                inc(i);
                j:=j-1;
             end;
         until i>j;
         if l<j then
           sort(l,j);
         if i<r then
           sort(i,r);
      end;

function min(a,b:data):data;
begin
        if a<b then exit(a);
        exit(b);
end;

procedure xuli;
var     i,j,res:data;
begin
        suma[0]:=0;
        sumb[0]:=0;
        d[0]:=0;
        for i:=1 to n do
                begin
                        if id[i]=1 then
                                begin
                                        suma[i]:=1;
                                        sumb[i]:=0;
                                end
                        else
                                begin
                                        suma[i]:=0;
                                        sumb[i]:=1;
                                end;
                end;
        for i:=1 to n do
                begin
                        suma[i]:=suma[i-1]+suma[i];
                        sumb[i]:=sumb[i-1]+sumb[i];
                end;
        vt[0]:=1;
        res:=high(data);
        for i:=1 to n do
                begin
                        vt[i]:=vt[i-1];
                        for j:=vt[i-1] to i-1 do
                                if (suma[i]-suma[j-1]>=a) and (sumb[i]-sumb[j-1]>=b) then
                                        begin
                                                vt[i]:=j;
                                                res:=min(res,d[i]-d[j]);
                                        end
                                else
                                        break;
                end;
        if res=high(data) then
                writeln(-1)
        else
                writeln(res);
end;


begin
        docfile;
        sort(1,n);
        xuli;
end.

MINROAD spoj VOI2014 – Con duong Tung Truc