Codeforces 855 B Marvolo Gaunt's Ring
题目链接
题目大意:
给出三个数p,q,r,和一个n个数的数组a[],求 p·ai + q·aj + r·ak的最大值,其中1 ≤ i ≤ j ≤ k ≤ n.
发牢骚：
一开始没看到i,j,k有顺序关系然后wa了两发（难受）。过了之后一早起来发现wa了,原来最小值初始化小了（难受）。
直接掉rating了。
分析:
对于p，q，r三个数来说，如果与q相乘的aj 确定了那么ai必定在[1,j],ak必定在[j,n]。
如果q>=0，那么ai就是在[1,j]的最大值，如果q<0，则ai就是在[1,j]的最大值。ak同理。
因为给出的数组a不一定是单调序列所以不能二分查找,但n的范围是1e5,想快点查找就想到上rmq了（线段树貌似也行）。
然后可想而知就是预处理出a[]的rmq数组maxs[]和mins[]，然后枚举aj来确定ai和ak。
总时间复杂度是O(nlogn（rmq预处理）+n（枚举aj））
有个细节就是初始化ans时其值必须小于-3*1e18，因为p,q,r和a[]范围是1e-9--1e9，可想而知最小值为-3*1e18。
#include<iostream>
#include<string>
#include<cstring>
#include<vector>
#include<map>
#include<algorithm>
#include<queue>
#include<set>
#include<cstdio>
#include<functional>
#include<iomanip>
#include<cmath>
#include<stack>
#define mod 1030
#define size 3
using namespace std;
typedef long long LL;
const int maxn = (LL)1e5 + 100;
const int maxm = 50000;
const LL inf = (LL)6 * LL(1e18);
const double eps = 1e-8;
int mp[maxn];
struct rmq {
int maxs[maxn][20], mins[maxn][20];
int n;
void read(int _n) {
n = _n;
for (int i = 1; i <= n; i++) {
scanf("%d", &mp[i]);
maxs[i][0] = mp[i];
mins[i][0] = mp[i];
}
}
void pre() {
int top = (int)(log(n * 1.0) / log(2.0));
for (int j = 1; j <= top; ++j)
for (int i = 1; i <= n; ++i)
if (i + (1 << j) - 1 <= n) {
maxs[i][j] = max(maxs[i][j - 1], maxs[i + (1 << (j - 1))][j - 1]);
mins[i][j] = min(mins[i][j - 1], mins[i + (1 << (j - 1))][j - 1]);
}
}
int querymax(int i, int j) {
int k = (int)log2(j - i + 1.0), l = j - (1 << k) + 1;
return max(maxs[i][k], maxs[l][k]);
}
int querymin(int i, int j) {
int k = (int)log2(j - i + 1.0), l = j - (1 << k) + 1;
return min(mins[i][k], mins[l][k]);
}
}rmqs;
int main() {
LL p, q, r;
int n;
while (scanf("%d", &n) == 1) {
scanf("%I64d%I64d%I64d", &p, &q, &r);
rmqs.read(n);
rmqs.pre();
LL ans = -inf;
for (int i = 1; i <= n; i++) {
LL tmp = q*mp[i];
if (p >= 0) tmp += p*(LL)rmqs.querymax(1, i);
else tmp += p*(LL)rmqs.querymin(1, i);
if (r >= 0) tmp += r*(LL)rmqs.querymax(i, n);
else tmp += r*(LL)rmqs.querymin(i, n);
ans = max(ans, tmp);
}
printf("%I64dn", ans);
}
}
相关知识
专题一 CodeForces
Bird Toys Parrot Pet Swing Cotton Toy Ring Parrot Stand Bird Toy
西宠展。中国WCCF国际纯种猫品鉴赛，西安站12环赛:荣获S
s=“abcdefg”,s[2]的值是“b”。
基于B/S架构宠物领养管理系统设计
彩虹岛宠物等级分为S、A、B、C四种，其中S级最高，C级最低
Stainless Steel Bird Rings Outdoor Fly Training Activity Accessories Pet Birds Leash Foot Rings Parrot Flying Pigeon Leg Ring
三角形面积=SQRT(S*(S
[勤学好问] 求问小宠物类型 S/B是什么意思 NGA玩家社区
如图所示，匀强电场的电场强度E=2.0×104N/C，沿电场线方向有A、B两点，A、B两点间的距离s=0.10m。将电荷量q=+2.0×10
网址: Codeforces 855 B Marvolo Gaunt's Ring https://m.mcbbbk.com/newsview1121857.html
| 上一篇: 春季上火吃什么下火 不妨试试五款 |
下一篇: 如何让哈士奇健康度过春季换季时期 |
