hdu5662 YJQQQAQ and the function (单调栈)
2024-08-31 23:33:13
Problem Description
YJQQQAQ has an array A of
length n.
He defines a function fl,r,k where l,r,k are
positive integers that satisfies l≤r and r×k≤n,
and the value of the function equals to p×q×⌊k√⌋ where p equals
to the sum value of Al×k,A(l+1)×k,...,Ar×k and q equals
to the minimal value of them. YJQQQAQ wants to choose the positive integers l,r,k carefully
to maximize the value of the function.
length n.
He defines a function fl,r,k where l,r,k are
positive integers that satisfies l≤r and r×k≤n,
and the value of the function equals to p×q×⌊k√⌋ where p equals
to the sum value of Al×k,A(l+1)×k,...,Ar×k and q equals
to the minimal value of them. YJQQQAQ wants to choose the positive integers l,r,k carefully
to maximize the value of the function.
Input
The first line contains an integer T(1≤T≤3)——The
number of the test cases. For each test case:
The first line contains an integers n(1≤n≤300,000).
The second line contains n integers
describing the given array A,
the ith
integer is Ai(1≤Ai≤1,000,000).
Between each two adjacent integers there is a white space separated.
number of the test cases. For each test case:
The first line contains an integers n(1≤n≤300,000).
The second line contains n integers
describing the given array A,
the ith
integer is Ai(1≤Ai≤1,000,000).
Between each two adjacent integers there is a white space separated.
Output
For each test case, the only line contains the only integer that is the maximum value of the function.
Sample Input
1
3
2 3 1
3
2 3 1
Sample Output
10
题意:给你n个数,你要找到3个数,l,r,k,l<=r,r*k<=n且p*q*sqrt(k)最小,其中p是A[l*k],A[(l+1)*k]...,A[r*k]的和,q是这些数的最小值。
思路:看到求一些数的和乘这些数中最小值的最小值,容易想到单调栈,我们只要先把在k确定的情况下找出所有符合条件的A[],然后再用单调栈找出以每一个数位最小值的左右边界,然后更新ans的最大值就行了。ps:还是不习惯用单调栈,所以用两遍单调队列做了,时间复杂度会差一下,不过差不多。
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<bitset>
#include<algorithm>
using namespace std;
#define lth th<<1
#define rth th<<1|1
typedef long long ll;
typedef long double ldb;
#define inf 99999999
#define pi acos(-1.0)
#define maxn 300050
int b[maxn],a[maxn];
ll sum[maxn];
int L[maxn],R[maxn];
int q[511111][2];
int main()
{
int n,m,i,j,T,l,r,k;
int front,rear;
ll ans;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d",&a[i]);
}
ans=0;
for(k=1;k<=n;k++){
int tot=0;
sum[0]=0;
for(i=1;i*k<=n;i++){
tot++;
b[tot]=a[i*k];
sum[tot]=sum[tot-1]+b[tot];
}
front=1,rear=0;
for(i=1;i<=tot;i++){
while(front<=rear && q[rear][0]>=b[i] ){
rear--;
}
if(rear==0){
L[i]=1;
}
else{
L[i]=q[rear][1]+1;
}
rear++;
q[rear][0]=b[i];q[rear][1]=i;
}
front=1,rear=0;
for(i=tot;i>=1;i--){
while(front<=rear && q[rear][0]>=b[i] ){
rear--;
}
if(rear==0){
R[i]=tot;
}
else{
R[i]=q[rear][1]-1;
}
rear++;
q[rear][0]=b[i];q[rear][1]=i;
ans=max(ans,(sum[R[i] ]-sum[L[i]-1 ])*b[i]*(int)sqrt((double)k) );
}
}
printf("%lld\n",ans);
}
return 0;
}
最新文章
- iOS检测用户截屏并获取所截图片
- iOS开发UI篇—使用UItableview完成一个简单的QQ好友列表(二)
- 复制”链接文件“到虚拟机(VirtualBox)的”共享文件夹“时报错:创建符号链接时报错:只读文件系统
- Python爬虫预备知识
- 织梦dedecms|图片模型内容页标签
- 深入探索C++对象模型(三)
- 针对Oracle数据库中SCOTT方案的多表查询一个例子
- SQL server查询语句
- MariaDB与MySQL
- 关于sql的查询操作记录
- Java设计模式之《构建者模式》及应用场景
- Git合并指定文件到另一个分支
- react-native init的时候出现问题:npm WARN React-native@0.35.0 requires a peer of react@~15.3.1 but none was
- <;Linux>; Ubuntu error: ssh: connect to host master port 22: No route to host lost connection
- BitCoinCore配置文件解读
- myeclipse解决Fail to create the java Virtual Machine
- Android之代码创建布局
- lodop 二维码内容多少
- 读取和修改app.config文件
- AIR:使用 HTML + Javascript 开发桌面应用