Với mỗi i, tính giá tiền nhỏ nhất từ ngày 1 đến ngày i, cộng vào đáp số giá tiền đó nhân với số tấn cần mua. Cách này chỉ cần dùng 5 biến N, minCost(giá tiền nhỏ nhất), cost(giá tiền mỗi ngày), ton(số tấn cần mua mỗi ngày), res(đáp số). ĐPT thời gian: O(N).
ll res = 0, minCost = INF, cost, ton;
while (N --) {
cin >> ton >> cost;
minimize(minCost, cost);
res += minCost * ton;
}
Bình luận
Hint
Với mỗi i, tính giá tiền nhỏ nhất từ ngày 1 đến ngày i, cộng vào đáp số giá tiền đó nhân với số tấn cần mua. Cách này chỉ cần dùng 5 biến N, minCost(giá tiền nhỏ nhất), cost(giá tiền mỗi ngày), ton(số tấn cần mua mỗi ngày), res(đáp số). ĐPT thời gian: O(N).
4 bình luận nữa