注1:繁星还是编程萌新,欢迎各位大佬指点。
注2:繁星于昨天刚考完,理论上此题应该正确,但是由于算法不是最优,近半测试点都超时(时限1秒)。
题目与程序:________
一、题目
策略游戏(game)
【题目描述】
—-小 L 和小 Q 在玩一个策略游戏。
—-有一个长度为 n 的数组 A 和一个长度为 m 的数组 B ,在此基础上定义一个大小为 n × m 的矩阵 C ,满足 Cij = Ai × Bj。所有下标均从 1 开始。
—-游戏一共会进行 q 轮,在每一轮游戏中,会事先给出 4 个参数 l1, r1, l2, r2,满足1 ≤ l1 ≤ r1 ≤ n, 1 ≤ l2 ≤ r2 ≤ m。
—-游戏中,小 L 先选择一个 l1 ∼ r1 之间的下标 x,然后小 Q 选择一个 l2 ∼ r2 之间的下标 y。定义这一轮游戏中二人的得分是 Cxy。
—-小 L 的目标是使得这个得分尽可能大,小 Q 的目标是使得这个得分尽可能小。同时两人都是足够聪明的玩家,每次都会采用最优的策略。
—-请问:按照二人的最优策略,每轮游戏的得分分别是多少?
【输入格式】
—-从文件 game.in 中读入数据。
—-第一行输入 3 个正整数 n, m, q,分别表示数组 A,数组 B 的长度和游戏轮数。
—-第二行:n 个整数,表示 Ai,分别表示数组 A 的元素。
—-第三行:m 个整数,表示 Bi,分别表示数组 B 的元素。
—-接下来 q 行,每行 4 个正整数,表示这一次游戏的 l1, r1, l2, r2。
【输出格式】
—-输出到文件 game.out 中。
—-输出共 q 行,每行一个整数,分别表示每一轮游戏中,小 L 和小 Q 在最优策略下的得分。
【数据范围】
—-对于所有数据,保证 5 ≤ n ≤ 2500, 1 ≤ m ≤ 10000, 0 ≤ k ≤ 100, 所有景点的分数1 ≤ si ≤ 1018。保证至少存在一组符合要求的行程。
二、程序
//作者:繁星(www.stars22.xyz)
#include<bits/stdc++.h>
using namespace std;
int n,m,q;//数组 A长度,数组 B 长度,游戏轮数
int min0=-1000000001,max0=1000000001;//需要用到的最大值最小值(此处应为常量)
int a[100001],b[100001];//数组A,数组B
int l1,l2,r1,r2;//小L和小Q选择的范围
long long min1,min2,max1,max2,mina1,mina2,minb1,minb2;
//l1~ri中:min1:最小值,max1:最大值,mina1:绝对值最小的正数,minb1:绝对值最小的负数
//l2~r2中:min2:最小值,max2:最大值,mina2:绝对值最小的正数,minb2:绝对值最小的负数
int minmax(){//赋初始值
min1=max0;
min2=max0;
max1=min0;
max2=min0;
mina1=max0;
mina2=max0;
minb1=min0;
minb2=min0;
return 0;
}
int incl(){//进行挑选
cin>>l1>>r1>>l2>>r2;
minmax();
for(int i=l1;i<=r1;i++){
if(a[i]<min1){
min1=a[i];
}
if(a[i]>max1){
max1=a[i];
}
if(a[i]<0&&a[i]>minb1){
minb1=a[i];
}
if(a[i]>=0&&a[i]<mina1){
mina1=a[i];
}
}
for(int i=l2;i<=r2;i++){
if(b[i]<min2){
min2=b[i];
}
if(b[i]>max2){
max2=b[i];
}
if(b[i]<0&&b[i]>minb2){
minb2=b[i];
}
if(b[i]>=0&&b[i]<mina2){
mina2=b[i];
}
}
return 0;
}
int game(){//进行比较选出方案
if(min2<0&&max2>0){
long long maxout1=mina1*min2,maxout2=minb1*max2;
if(maxout1<maxout2)cout<<maxout2;
else cout<<maxout1;
}
if(min2>=0&&max1>=0){
cout<<max1*min2;
}
if(min2>=0&&max1<0){
cout<<max1*max2;
}
if(max2<=0&&min1<=0){
cout<<min1*max2;
}
if(max2<=0&&min1>0){
cout<<min1*min2;
}
return 0;
}
int main(){
freopen("game.in","r",stdin);
freopen("game.out","w",stdout);
cin>>n>>m>>q;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=m;i++){
cin>>b[i];
}
for(int i=1;i<=q;i++){
incl();
game();
cout<<endl;
}
return 0;
}