Bài toán địa điểm du lịch Dailai nổi tiếng với con đường Tùng - Trúc bằng C/C++

Bài toán địa điểm du lịch Dailai nổi tiếng với con đường Tùng - Trúc bằng C/C++

Đị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 ở vị trí có khoảng cách đến vị trí bắt đầu con đường là di (i = 1, 2, …, n). Với kinh phí có hạn, Ban quản lý muốn chọn đ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 đó có ít nhất a cây tùng và có ít nhất b cây trúc.

Dữ liệu: Vào từ file văn bản MINROAD.INP:

* 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 di (di ≤ 109) và ki, trong đó di là khoảng cách của cây tính từ vị trí bắt đầu của con đường, ki = 1 nếu là cây tùng, ki = 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.

Kết quả: Ghi ra file văn bản MINROAD.OUT 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.

[Input example]

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

[Output example]

35

Giải thuật

* Sắp xếp dãy vị trí của các cây theo thứ tự tăng dần: d[1] < d[2] <...

* Bắt đầu từ đầu dãy, duyệt từ trái qua phải để tìm các đoạn gồm dãy các phần tử liên tiếp chứa ít nhất a cây tùng và ít nhất b cây trúc. Mỗi lần tìm được đoạn như vậy ghi nhận độ dài để tìm ra đoạn ngắn nhất.

Cài đặt

#include <cstdio>

#include <iostream>

#include<stdlib.h>

using namespace std;

#define nmax 300000

long data[nmax][2];

int compare(const void *arg1, const void *arg2)

{

 int const *lhs = static_cast<int const*>(arg1);

 int const *rhs = static_cast<int const*>(arg2);

 return (lhs[0] < rhs[0]) ? -1

  : ((rhs[0] < lhs[0]) ? 1

  : (lhs[1] < rhs[1] ? -1

  : ((rhs[1] < lhs[1] ? 1 : 0))));

};

int main(int argc, char** argv)

{

 freopen("MINROAD.INP", "r", stdin);

 freopen("MINROAD.OUT", "w", stdout);


 int n, a, b;

 scanf("%d %d %d", &n, &a, &b);

 if (a == 0 && b == 0){

  printf("%d", -1);

  return 0;

 }

 for (int i = 0; i < n; i++)

  scanf("%d %d", &data[i][0], &data[i][1]);


 qsort(data, n, 2 * sizeof(int), compare);


 long min = 1000000000;

 int head, tail = 0;

 int countTung = 0;

 int countTruc = 0;


 for (int i = 0; i < n; i++){

  if (data[i][1] == 1){

   countTung++;

  }

  else{

   countTruc++;

  }

  if (countTung >= a && countTruc >= b){

   head = i;

   min = data[head][0] - data[tail][0];

   break;

  }

 }


 bool isSub = false;

 while (head < n){

  for (int j = tail; j < head; j++){

   isSub = false;

   if (data[j][1] == 1 && countTung >a){

    countTung --;

    tail += 1;

    isSub = true;

   }

   if (data[j][1] !=1 && countTruc >b){

    countTruc--;

    tail += 1;

    isSub = true;

   }

   if(!isSub) break;

   if (data[head][0] - data[tail][0] < min){

     min = data[head][0] - data[tail][0];

    }


  }

  head++;

  if (head < n){

   if (data[head][1] == 1){

    countTung++;

   }

   else{

    countTruc++;

   }

  }

 }

 if (min == 1000000000){ min = -1; }

 printf("%d", min);

 return 0;

}
Bạn thấy bài viết này như thế nào?: 
Average: 10 (6 votes)
Ảnh của Tommy Tran

Tommy Tran owner Express Magazine

Drupal Developer having 9+ year experience, implementation and having strong knowledge of technical specifications, workflow development. Ability to perform effectively and efficiently in team and individually. Always enthusiastic and interseted to study new technologies

  • Skype ID: tthanhthuy
  • Phone/Zalo: (+84) 944 225 212
  • WhatsApp: (+84) 944 225 212
  • Line Messenger: (+84) 944 225 212
  • Email: [email protected]
  • Telegram Messenger: https:/t.me/tommytran0401

Advertisement

 

jobsora

Dich vu khu trung tphcm

Dich vu diet chuot tphcm

Dich vu diet con trung

Quảng Cáo Bài Viết

 
Startup công nghệ tỉ đô đầu tiên của châu Phi lên sàn chứng khoán New York

Startup công nghệ tỉ đô đầu tiên của châu Phi lên sàn chứng khoán New York

Theo CNBC, cổ phiếu Jumia Technologies tăng đến hơn 60% trong ngày đầu giao dịch trên Sàn Giao dịch Chứng khoán New York. Giữa ngày giao dịch (giờ Mỹ) cổ phiếu có giá tầm 22 USD, cao hơn mức mở cửa 14,5 USD. Vốn hóa thị trường của Jumia hơn 1 tỉ USD một chút.

Tuyệt chiêu vào Facebook bằng Gmail

Tuyệt chiêu vào Facebook bằng Gmail

Có lẽ các chiêu thức đổi DNS hay chỉnh sửa file host đã quá nổi tiếng trên mạng nên hôm nay, chúng tôi xin giới thiệu một độc chiêu vào Facebook hoàn toàn..

Khuyên bạn nên sử dụng 15 Outstanding Drupal Modules

Khuyên bạn nên sử dụng 15 Outstanding Drupal Modules

Drupal is a (CMS) any web developer should get to know. It is in my opinion the best open source CMS available at the moment, and it has a huge community of contributors

Wordpress Freelancer

 

Wordpress Freelancer