傳送門

文章目錄

• 題意：
• 思路：

題意：

給你平面上$n$個點，你需要對于$1?n$依次選擇$n$個點作為每個點的終點，滿足選擇的點$i<j,x_i\le x_j,y_i\le y_j$，最小化每個點的起點到終點的距離平方總和。

$n\le 1e5,s_i,t_i\le 1e6$

思路：

考慮貢獻的公式$(x_s?x_t{)}^2+(y_s?y_t{)}^2$，不難發(fā)現(xiàn)對于$x,y$坐標來說，貢獻是分開的，所以我們分開來考慮這個問題。

現(xiàn)在只考慮$x$軸，也就是給你一段序列，你需要選擇一個單調(diào)不減的下標，使得每個點到其對應點的距離平方和最小。

假設原序列為$a$，你構造的序列為$b$，那么如果原序列遞增的話，顯然$b$直接取與$a$相等是最優(yōu)的，這時答案為$0$。

當然上述是特殊情況，我們需要考慮如果$a$序列在某段遞減怎么辦呢？顯然我們不能取太大，也不能取太小，我們一定是取他們的平均數(shù)來作為這段遞減區(qū)間的終點，因為$a$遞減，$b$需要遞增，所以一定是這一段都取某個數(shù)，并且由于平方上升的很快，所以肯定讓這幾個數(shù)最大平方數(shù)越小越好，所以就是他們的平均數(shù)了。

那么現(xiàn)在我們解決了某一段，如果下一個數(shù)比平均數(shù)小怎么辦？顯然我們將其加入平均數(shù)的集合再取個平均數(shù)即可。

可以發(fā)現(xiàn)這個過程就是單調(diào)棧一個經(jīng)典過程，所以直接維護一下就好了。

// Problem: A - Access Points // Contest: Virtual Judge - Namomo Summer Camp Day 4 // URL: https://vjudge.net/contest/455214#problem/A // Memory Limit: 262 MB // Time Limit: 1000 ms // // Powered by CP Editor (https://cpeditor.org)//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native") //#pragma GCC optimize(2) #include<cstdio> #include<iostream> #include<string> #include<cstring> #include<map> #include<cmath> #include<cctype> #include<vector> #include<set> #include<queue> #include<algorithm> #include<sstream> #include<ctime> #include<cstdlib> #include<random> #include<cassert> #define X first #define Y second #define L (u<<1) #define R (u<<1|1) #define pb push_back #define mk make_pair #define Mid ((tr[u].l+tr[u].r)>>1) #define Len(u) (tr[u].r-tr[u].l+1) #define random(a,b) ((a)+rand()%((b)-(a)+1)) #define db puts("---") using namespace std;//void rd_cre() { freopen("d://dp//data.txt","w",stdout); srand(time(NULL)); } //void rd_ac() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//AC.txt","w",stdout); } //void rd_wa() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//WA.txt","w",stdout); }typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> PII;const int N=1000010,mod=1e9+7,INF=0x3f3f3f3f; const double eps=1e-6;int n; double a[N],b[N],ans; struct Node{int l,r;double ave; }stk[N]; int top;int sgn(double x) {if(x<eps) return 0;return x>0? 1:-1; }void solve(double a[]) {top=0;for(int i=1;i<=n;i++) {if(!top) stk[++top]={i,i,a[i]};else {int l=i,r=i;double ave=a[i];while(top&&sgn(stk[top].ave-ave/(r-l+1))>0) {l=stk[top].l; ave+=stk[top].ave*(stk[top].r-stk[top].l+1);top--;}stk[++top]={l,r,ave/(r-l+1)};}}for(int i=1;i<=top;i++) {for(int j=stk[i].l;j<=stk[i].r;j++) {ans+=(stk[i].ave-a[j])*(stk[i].ave-a[j]);}} }int main() { // ios::sync_with_stdio(false); // cin.tie(0);scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%lf%lf",&a[i],&b[i]);solve(a); solve(b);printf("%.10f\n",ans);return 0; } /**/

總結

以上是生活随笔為你收集整理的NWERC 2018 A. Access Points 二维转一维 + 单调栈的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。