HDU 4791 Alice's Print Service
从后往前预处理打印纸的最小花费。然后在询问时通过upper_bound找到位置p，比较当前打印纸张花费与相邻临界点最小花费即可。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <cmath>
#include <set>
using namespace std;
int T;
const int maxn = 100010;
const int INF = 0x3f3f3f3f;
typedef long long LL;
LL x[maxn], y[maxn];
LL cost[maxn];
int main()
{
int T;
for(scanf("%d", &T); T > 0; T--)
{
int n, m;
scanf("%d%d", &n, &m);
for(int i = 0; i < n; i++)
{
scanf("%I64d%I64d", &x[i], &y[i]);
cost[i] = x[i]*y[i];
}
LL pre = cost[n-1];
for(int i = n-1; i >= 0; i--)
{
if(pre < cost[i])
{
cost[i] = pre;
pre = cost[i];
}
}
while(m--)
{
LL q; scanf("%I64d", &q);
if(q >= x[n-1]) { printf("%I64d\n", q*y[n-1]); continue ; }
LL p = upper_bound(x, x+n, q)-x;
LL ans = q*y[p-1];
ans = min(ans, cost[p]);
printf("%I64d\n", ans);
}
}
return 0;
}
2022年8月18日 14:08
JAC 12th Question Paper 2023 Download – JAC Intermediate Important Question Paper 2023 PDF, Jharkhand JAC Intermediate Important Question Paper 2023 PDF Academic Council which is also abbreviated as JAC is one of the biggest education board for school which provides school education to students and responsible for conducting the examinations for the 10th and 12th class which is also called Intermediate.
2023年1月09日 13:08
Alice recently started her own print service, and she wants to offer the best possible service to her customers. She knows that the quality of her prints is important, but she also knows that price is a major factor for many design own engagement ring customers. She's currently struggling to find the perfect balance between quality and price. Alice is currently experimenting with different paper types and printing techniques to find the best combination of quality and price. She's also working on ways to speed up her production process so that she can keep her prices low while still delivering high-quality prints.