Kiến trúc sư và con đường

View as PDF

Submit solution


Points: 200 (partial)
Time limit: 1.0s
Memory limit: 1G
Input: stdin
Output: stdout

Author:
Problem types

Một công ty xây dựng nọ đang lên kế hoạch cho việc sữa chữa một con đường cao tốc có chiều dài là \(n\) kilomet. Con đường này được đánh số từ \(1\) đến \(n+1\) tại những vị trí cách đều nhau đúng \(1\) kilomet, bắt đầu từ vị trí đầu của con đường. Chi phí sửa chữa cho đoạn \(1\) kilomet từ vị trí \(i\) đến \(i+1\) là \(A_i\) với \(1 ≤ i ≤ n\).

Một kiến trúc sư người Ý đảm nhiệm vai trò này và đang khảo sát mức độ hư hại cũng như chi phí để sửa chữa con đường này. Do kinh phí thời điểm hiện tại không đủ để thi công một lúc cả con đường. Anh ấy kế hoạch tính toán để chọn ra đoạn đường phù hợp nhất để sửa chữa đầu tiên. Anh ấy khảo sát con đường bằng cách chọn ra một đoạn từ vị trí \(L\) đến vị trí \(R\) trên con đường và tính xem chi phí sửa chữa trung bình trên \(1\) kilomet của đoạn này là bao nhiêu.

Yêu cầu: Cho \(Q\) câu truy vấn \((L, R)\). Hãy tính chi phí sửa chữa trung bình trên \(1\) kilomet của vị trí \(L\) đến vị trí \(R\).

Dữ liệu vào

  • Dòng đầu tiên gồm số \(n\).
  • Dòng thứ hai gồm \(n\) số nguyên \(A_i\).
  • Dòng thứ ba là số \(Q\) – số lượng câu truy vấn.
  • Q dòng tiếp theo, mỗi dòng gồm 2 số \(L\) và \(R (L<R)\).

Kết quả

  • Gồm \(Q\) dòng tương ứng là kết quả của câu truy vấn thứ \(i\), kết quả được làm tròn đến chữ số thập phân thứ \(6\).

Sample Input 1

5
1 2 3 4 5
3
1 4
2 5
4 6

Sample Output 1

2.000000
3.000000
4.500000

Giới hạn

  • \(0 ≤ A_i ≤ 10^9\)
  • 70% test có \(1 ≤ q,n ≤ 10^3\).
  • 30% test có \(1 ≤ q,n ≤ 5*10^4\).

View comments (1)

Comments


  • 0
    SPyofgame  commented on 8:41 p.m. 14 jun, 2020 edited

    Spoiler Alert


    Hint 1
    • Trâu từng đoạn một

    Với mỗi truy vấn ta tính \(sum_{l..r} = \Sigma(l \leq i \leq r)\{a_i\}\)

    Độ dài đoạn là \(len = r - l\)

    Kết quả là trung bình cộng đoạn này: \(\frac{sum}{len}\)


    Hint 2
    • Sử dụng mảng cộng dồn

    Với \(a[i]_{sau} = \Sigma(1 \leq j \leq i)\{a[j]_{trước}\}\)

    Ta dễ dàng tính \(sum_{l..r}\)

    \(= \Sigma(l \leq i \leq r)\{a[i]_{trước}\} = \Sigma(1 \leq i \leq r)\{a[i]_{trước}\} - \Sigma(1 \leq i \leq l - 1)\{a[i]_{trước}\} = a[r]_{sau} - a[l - 1]_{sau}\)


    Reference AC code | \(O(n)\) time | \(O(1)\) query | \(O(n)\) auxiliary space | Query-problem, Prefix-sum
     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    int main()
    {
        /// Input
        int n = readInt();
        vector<ll> a(n + 1, 0); /// a[0] = 0
        for (int i = 1; i <= n; ++i) {
            cin >> a[i];      /// a[i] truoc
            a[i] += a[i - 1]; /// a[i] sau
        }
    
        /// Solve
        for (int q = readInt(); q--; )
        {
            int l, r;
            cin >> l >> r;
            cout << setprecision(6) << fixed << double(a[r - 1] - a[l - 1]) / (r - l) << '\n';
        }
        return 0;
    }