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

Xem PDF
Tác giả:
corona
Dạng bài
Điểm: 200 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

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 \le i \le 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\).

Input

  • 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)\).

Output

  • 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\).

Scoring

  • \(0 \le A_i \le 10^9\)
  • Subtask \(1\) (\(70\%\) số điểm): \(1 \le q,n \le 10^3\).
  • Subtask \(2\) (\(30\%\) số điểm): \(1 \le q,n \le 5*10^4\).

Example

Test 1

Input 
5
1 2 3 4 5
3
1 4
2 5
4 6
Output 
2.000000
3.000000
4.500000

Bình luận


  • 0
    SPyofgame    8:41 p.m. 14 Tháng 6, 2020 ← đã chỉnh sửa

    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

    C++
    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;
}