Tập xe

Xem PDF




Tác giả:
Dạng bài
Điểm: 300 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cô giáo trường tiểu học \(X\) đang dạy \(n\) học sinh tập xe đạp, các học sinh được đánh số từ \(1\) tới \(n\), học sinh thứ \(𝑗\) có trọng lượng là \(a_𝑗\). Có một xe đạp duy nhất với tải trọng là \(m\), hai học sinh chỉ có thể cùng lên xe nếu tổng trọng lượng của hai học sinh không vượt quá \(m\).

Cô giáo tự hỏi có bao nhiêu cách chọn hai học sinh khác nhau cho cùng lên xe, sau nhiều giờ tính toán không có kết quả, cô quyết định hỏi các chuyên gia lập trình giải bài toán Counting Student Pairs (CSP)

Yêu cầu: Đếm số cặp chỉ số \(i, j\) trong đó \(i < j\)\(a_i + a_j \leq m\)

Input

  • Dòng 1 chứa hai số nguyên dương \(n, m\ (m \leq 10^6)\)
  • Dòng 2 chứa \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\) (\(\forall{i}: a_i \leq 10^6\))

Output

Ghi một số nguyên duy nhất là đáp số

Scoring

  • Subtask #1 (\(60\%\) số điểm): \(n \leq 10^4\).
  • Subtask #2 (\(20\%\) số điểm): \(n \leq 10^5\).
  • Subtask #3 (\(20\%\) số điểm): \(n \leq 10^6\).

Example

Test 1

Input
5 6
1 2 3 4 5
Output
6

Bình luận

  • Sangnguyen 8:53 p.m. 1 Tháng 4, 2025

    include <bits/stdc++.h>

    using namespace std;

    int main(){
    ios::sync_with_stdio(false);cin.tie(NULL);
    long n,m,count=0;cin>>n>>m;
    vector<long> a(n);
    for(long i=0;i<n;i++){ cin>>a[i];
    }
    sort(a.begin(), a.end());
    long l=0,r=n-1;
    while(l<r){
    if(a[l]+a[r]<=m){
    count+=(r-l);
    l++;
    }else r--;
    }
    cout<<count;
    }

    • nvtd 7:40 a.m. 13 Tháng 2, 2025

      include <bits/stdc++.h>

      using namespace std;
      long long a[1000000];
      int main()
      {
      long long n, m, dem = 0;
      cin >> n >> m;
      for(int i = 1; i <= n; ++i) cin >> a[i];
      sort(a + 1, a + n + 1);
      for(int i = 1; i <= n; ++i) {
      int l = i + 1, r = n, j = -1;
      while(l <= r) {
      int mid = (l + r) / 2;
      if(a[i] + a[mid] <= m) {
      j = mid;
      l = mid + 1;
      } else r = mid - 1;
      }
      if(j != -1)
      dem += (j - i);
      }
      cout << dem;

      }

      • TruongQuangKhaicht1 9:14 p.m. 7 Tháng 10, 2024

        Code C++

        include<bits/stdc++.h>

        using namespace std;
        long long i,n,s,a[1123456],j,k=0,m,c;
        int main()
        {
        //freopen("a.inp","r",stdin);
        //freopen("a.out","w",stdout);
        cin>>n>>m;
        for(i=1;i<=n;i++)
        {
        cin>>a[i];
        }
        sort(a+1,a+1+n);
        for(i=1;i<=n;i++)
        {
        c=upper_bound(a+i+1,a+1+n,m-a[i])-a;
        s+=c-i-1;
        }
        cout<<s;
        }

        • HH_Nguyentrinhanhtien_2010 10:06 p.m. 2 Tháng 9, 2024

          ai đó cứu tôi
          toàn bị Runtime

          • TruongQuangKhaicht1 8:43 p.m. 26 Tháng 8, 2024 chỉnh sửa 5

            This comment is hidden due to too much negative feedback. Click here to view it.

            • kay 9:04 a.m. 15 Tháng 6, 2024

              import sys
              input = sys.stdin.read
              d = input().split()
              n = int(d[0])
              m = int(d[1])
              a = list(map(int, d[2:n+2]))
              a.sort()
              i, j = 0, n - 1
              count = 0
              while i < j:
              if a[i] + a[j] <= m:
              count += (j - i)
              i += 1
              else:
              j -= 1
              print(count)
              dùng pypy3 nhé

              • tranvanminhnhat123 8:27 p.m. 18 Tháng 5, 2024

                This comment is hidden due to too much negative feedback. Click here to view it.

                • xthabao1 9:00 p.m. 24 Tháng 4, 2024

                  This comment is hidden due to too much negative feedback. Click here to view it.

                  • tk22DoMinhVu 9:54 a.m. 24 Tháng 12, 2022

                    Làm giáo viên cũng khó nhỉ:)

                    • jumptozero 7:43 a.m. 24 Tháng 4, 2021 đã chỉnh sửa

                      Mình xin chia sẻ lời giải bài này như sau:

                      Đầu tiên, ta có nhận xét rằng, việc sắp xếp lại thứ tự các phần tử của mảng theo thứ tự tăng dần không làm ảnh hưởng đến kết quả của bài toán !

                      Tiếp theo, ý tưởng của bài này là sử dụng tìm kiếm nhị phân như sau:

                      • Ta có: \(a_i+a_j\le m (\text{ }0\le i<j<n)\implies a_j\le m-a_i(\text{ }0\le i<j<n)\)

                      Gọi \(P(j,i)\) là số phần tử \(a_j\) thoả mãn \(a_j\le m-a_i\)\(Q(j,i)\) là số phần tử \(a_j\) thoả mãn \(a_j>m-a_i\)

                      Khi đó ta có: \(P(j,i)+Q(j,i)=n-i+1 (\text{ với }0\le i<j<n)\).

                      Và để tính được \(Q(j,i)\) ta sử dụng chặt nhị phân để tìm. Và sau khi tính được \(Q(j,i)\) ta dễ dàng suy ra được \(P(j,i)\)

                      Và kết quả của bài toán chính là: \(\sum\limits_{0\le i<j<n}P(j,i)\)

                      Độ phức tạp của bài toán là: \(O(nlog(n))\)

                      Các bạn có thể tham khảo code tại đây: Link

                      Chú ý: Ở trong code của mình có sử dụng hàm: upper_bound, chính là hàm tìm kiếm nhị phân, các bạn có thể tự tìm hiểu thêm về những hàm tương tự như: lower_bound,...

                      Ps: Nếu có gì thắc mắc, các bạn cứ comment nhé

                      • 6 bình luận nữa