朝阳建设网站,龙江人社使用方法,电商运营培训视频课程,手机网站百度关键词排名正题
题目链接:https://www.luogu.com.cn/problem/T183637 题目大意
给出nnn个二元组(xi,yi)(x_i,y_i)(xi,yi)#xff0c;求最大的 ∣xi−xj∣min{∣yi∣,∣yj∣}|x_i-x_j|\times min\{|y_i|,|y_j|\}∣xi−xj∣min{∣yi∣,∣yj∣} 1≤n≤2106,−106≤xi≤106,−…正题
题目链接:https://www.luogu.com.cn/problem/T183637 题目大意
给出nnn个二元组(xi,yi)(x_i,y_i)(xi,yi)求最大的 ∣xi−xj∣×min{∣yi∣,∣yj∣}|x_i-x_j|\times min\{|y_i|,|y_j|\}∣xi−xj∣×min{∣yi∣,∣yj∣}
1≤n≤2×106,−106≤xi≤106,−109≤yi≤109,1≤T≤101\leq n\leq 2\times 10^6,-10^6\leq x_i\leq 10^6,-10^9\leq y_i\leq 10^9,1\leq T\leq 101≤n≤2×106,−106≤xi≤106,−109≤yi≤109,1≤T≤10 解题思路
昨天出去了所以没打比赛这个算法是那个时候口胡的。
首先时间复杂度显然不能带logloglog但是注意到xxx的范围这是在告诉我们可以拿xxx去排序。
xxx排好序之后我们发现对于一个位置jjj我们寻找一个ijijij使得答案最大那么显然iii要在从前往后的单调队列里。
这个其实启示了我们我们可以前后各维护一个单调栈然后在两个栈里面搞。
至于搞法不难发现决定因素是最小的那个所以我们每次把小的那个弹出顶部就好了。
时间复杂度O(n)O(n)O(n)。
然后交上去TTT了好多发以为是常数的问题结果换成题解的做法还是TTT了。
最后发现快读还不够要用那个文件的黑科技读入出题人真有你的 code
#includecstdio
#includecstring
#includealgorithm
#includevector
#includecctype
#define ll long long
using namespace std;
const int N2e610;
int T,n,a[N],sp[N],ss[N],tp,ts;
long long ans;
inline char Getchar()
{static char buf[100000],*p1buf100000,*pendbuf100000;if(p1pend){p1buf; pendbuffread(buf,1,100000,stdin);if (pendp1) return -1;}return *p1;
}
inline int read()
{char c;int d1;int f0;while(cGetchar(),!isdigit(c))if(c45)d-1;f(f3)(f1)c-48;while(cGetchar(),isdigit(c)) f(f3)(f1)c-48;return d*f;
}
void GetAns(int i,int j)
{ansmax(ans,1ll*(i-j)*min(a[i],a[j]));}
signed main()
{Tread();while(T--){nread();ans0;memset(a,0,sizeof(a));for(int i1;in;i){int xread()1e6,yread();a[x]max(a[x],abs(y));}tstp0;for(int i0;i2e6;i){if(!a[i])continue;while(ts0a[i]a[ss[ts]])ts--;ss[ts]i;}for(int i2e6;i0;i--){if(!a[i])continue;while(tp0a[i]a[sp[tp]])tp--;sp[tp]i;}int hp1,hs1;while(tstp){GetAns(ss[ts],sp[tp]);if(ts0a[ss[ts]]a[sp[tp]])ts--;else tp--;}printf(%lld\n,ans);}return 0;
}
