Khu sinh thái Funny chuẩn bị tiếp đón một đoàn khách đến tham quan m giống cây mới (được đánh số từ 1 đến m) do nhà khoa học Dante lai ghép được. Có n chậu câ
Khu sinh thái Funny chuẩn bị tiếp đón một đoàn khách đến tham quan m giống cây mới (được đánh số từ 1 đến m) do nhà khoa học Dante lai ghép được. Có n chậu cây, mỗi chậu trồng 1 loại cây trong số m loại giống trên (nm). Có thể coi các cây được trồng trên một đường thẳng trên trục số: chậu thứ i đặt ở tọa độ x_i và trồng loại cây a_i (1a_im. Dante được chỉ định sẽ dẫn đoàn khách đi tham quan. Do khách đã đi khảo sát ở nhiều nơi nên họ muốn đi một quãng đường có độ dài ngắn nhất tính từ vị trí cây được thăm đầu tiên để có thể thăm được tất cả m loại giống cây mới có trong vườn. Yêu cầu: Hãy chỉ cho Dante độ dài ngắn nhất mà đoàn khách cần di chuyển để có thể thăm được hết m loại giống cây mới này. Dữ liệu: Vào từ file văn bản MINDIS.INP Dòng đầu gồm 2 số n,m (n10^5,m10^5 ). n dòng tiếp theo, mỗi dòng gồm 2 số x_i,a_i là tọa độ và loại cây trồng tại x_i 0x_i10^9,0<a_im). Kết quả: Ghi ra file văn bản MINDIS.OUT gồm 1 số duy nhất là khoảng cách ngắn nhất mà đoàn khách cần di chuyển để có thể thăm được tất cả các loại cây mới trong vườn nhà Dante. Input: 7 3 25 2 26 1 15 1 22 3 20 1 30 1 27 3 Output: 2
Lời giải 1 :
bạn thử xem có đúng ko =)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,m,y,d,ans=1e10;
vector<vector<ll>> a(100005,vector<ll>(2));
int x[100005];
bool f[100005];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m;
for (int i=1;i<=n;i++)
cin>>a[i][0]>>a[i][1];
sort(a.begin()+1,a.begin()+n+1);
y=1;
// for (int i=1;i<=n;i++)
// cout<<a[i][0]<<' '<<a[i][1]<<'\n';
for (int i=1;i<=n;i++) {
if (x[a[i][1]]==0){
x[a[i][1]]=i;
d++;
} else {
f[x[a[i][1]]]=true;
x[a[i][1]]=i;
}
while(f[y]) y++;
if (d==m) {
ans=min(ans,a[i][0]-a[y][0]);
}
// cout<<ans<<'\n';
}
cout<<ans;
}
Thảo luận
Có thể bạn quan tâm
Bạn có biết?
Tin học, tiếng Anh: informatics, tiếng Pháp: informatique, là một ngành khoa học chuyên nghiên cứu quá trình tự động hóa việc tổ chức, lưu trữ, xử lý và truyền dẫn thông tin của một hệ thống máy tính cụ thể hoặc trừu tượng (ảo). Với cách hiểu hiện nay, tin học bao hàm tất cả các nghiên cứu và kỹ thuật có liên quan đến việc mô phỏng, biến đổi và tái tạo thông tin.
Nguồn : Wikipedia - Bách khoa toàn thưTâm sự 10
Lớp 10 - Năm thứ nhất ở cấp trung học phổ thông, năm đầu tiên nên có nhiều bạn bè mới đến từ những nơi xa hơn vì ngôi trường mới lại mỗi lúc lại xa nhà mình hơn. Được biết bên ngoài kia là một thế giới mới to và nhiều điều thú vị, một trang mới đang chò đợi chúng ta.
Nguồn : ADMIN :))Xem thêm tại https://loigiaisgk.com/cau-hoi or https://giaibtsgk.com/cau-hoi
Copyright © 2021 HOCTAPSGK