Mọi người cho em hỏi cách xử lí bài này với
Tìm tổng lớn nhất sao cho chỉ khoảng cách từ 1 điểm được chọn tới các chỉ số <= k
Ví dụ n = 4, k = 3
| Giá trị | Chỉ số |
|---|---|
| 4 | 7 |
| 10 | 15 |
| 2 | 2 |
| 5 | 1 |
OUTPUT ==> 11 (Chọn điểm số 4 thì tổng lớn nhất 4+2+5 = 11 tương ứng với các chỉ số thoả mãn là 7, 2, 1 vì khoảng cách của chúng tới 4 đều <= 3)
Ý tưởng1: Em nghĩ là bài này sử dụng tìm kiếm nhị phân nhưng làm vẫn chưa thành công
Ý tưởng2 Duyệt Trâu bò cách này chỉ làm được 20-30% test…
Mong mn giúp đỡ
Chào bạn,
Bước đầu tiên bạn muốn được giúp đỡ là nêu ra vấn đề một cách rõ ràng.
là sao ạ ???
Mình không hiểu chỗ này: “chỉ khoảng cách” có nghĩa là như thế nào ?
Giới hạn của bài toán (n, k, …) là bao nhiêu?
Bảng giá trị có thể âm không ?
v.v…
Có phải ý bài toán của bạn là tìm các điểm sao cho tổng chúng lớn nhất và tồn tại ít nhất 1 điểm sao cho khoảng cách của tất cả các điểm ta chọn tới điểm đó <= k hay ko?
code trâu em ạ:
#include <bits/stdc++.h>
#define F first
#define S second
#define maxn 100010
using namespace std;
int n, k, res, kq(-1e9), cso;
pair <int, int> a[maxn];
int main()
{
freopen("INP.txt", "r", stdin);
freopen("OUT.txt", "w", stdout);
cin >> n >> k;
int cmp1 = 1e9, cmp2 = -1e9;
for(int i = 1; i <= n; i++){
cin >> a[i].F >> a[i].S;
cmp1 = min(cmp1, a[i].S);
cmp2 = max(cmp2, a[i].S);
}
for(int i = cmp1; i <= cmp2; i++){
res = 0;
for(int j = 1; j <= n; j++){
if (abs(a[j].S - i) <= k) res += a[j].F;
}
if (res >= kq){
kq = res;
cso = i;
}
}
cout << kq << " " << cso;
return 0;
}
:(((( giúp em với đăng đề thì bị ban :((((((
:(((( chưa học cây IT ạ :(((( còn cách nào giải quyết không ạ
chỉ số dương hết ạ còn max kia thì chưa biết
Không bị “ban” gì hết, nếu đăng đề mà chỉ nhờ giải giùm thì bị khóa bài.
Bài của bạn có đề và mục đích của bạn là nhờ định hướng để thực hiện giải thuật là tốt.
chạy chỉ số là như nào ạ
theo cách nói như trên thì
VD OUTPUT
4 3
4 7
10 15
2 2
5 1
B1 sort
5 1
2 2
4 3
4 7
10 15
B2 tạo mảng S
s[1] 5
s[2] 7
s[3] 11
s[4] 15
s[5] 25
B3 chạy mỗi chỉ số là chạy xi 1 2 3 7 15 ạ ???
B4 sau khi tìm đc k tìm max từ i đến k là khoảng cách từ i đến k hay max của gì ạ
bạn diễn giải bằng output ví dụ đuọc không cảm ơn ạ
À sorry bạn mình hiểu nhầm đề. Bạn chỉ cần tạo mảng S[i] là số nấm từ 1 đến i.
chưa hiểu chỗ với mỗi i tìm đc j lớn nhất sao cho x[j] - x[i] <= 2*k chỗ này chặt nhị phân được ạ
Đổi vế sang sẽ là x[j] <= x[i] + 2 * k. Mảng x tăng dần là tiền đề cho việc chặt nhị phân ở đây!
hình như kq lớn nhất mỗi i không phải là s[j] - s[i-1] mình thử r
Hi @hihihihi
@SITUVN.gcd có đề cập ở trên, tuy nhiên, tớ xin phép giải thích rõ hơn, để giúp cậu giải đáp thắc mắc của cậu.
Cậu hoàn toàn có thể up đề bài lên, nhưng cậu cần phải:
Nếu cậu chỉ up mỗi đề bài lên, mà không có đưa ra nỗ lực giải quyết, cũng không có bất cứ code nào, cậu sẽ bị hiểu là nhờ làm bài tập hộ. Đó không phải practice tốt cho sự nghiệp lập trình, và để không khuyến khích lớp lập trình viên tiếp theo làm điều đó, bọn tớ reject các topic như vậy.
Hi vọng cậu đã hiểu cách diễn đạt mình hoạt động, và đưa ra câu hỏi phù hợp trong các post tiếp.
Chúc cậu có trải nghiệm tốt khi sử dụng diễn đàn!
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?