语音评测系统 2019 计蒜之道 初赛 第六场 多个特殊二次函数(同样形状)的最小值 它与多条直线最小值的互换
https://nanti.jisuanke.com/t/39458
n个函数的形状是一致的，只是大小不同
a按照从小到大排序，
设当前最小值的区间段为
(u1,u2) ai1
(u2,u3) ai2
……
[其中i1<i2<...]
加上一个新的函数，若它与函数ik交于点ur，则它必大于段(u1,u2),...,(uk-1,uk)，必小于段(uk+1,uk+2),(uk+2,uk+3),...。
经过修改过，段变为(u1,u2),...,(uk-1,uk),(uk,ur),(ur,inf)
使用单调栈处理，每个段最多被加入或删除一次
同理，对于函数(x+a)^2+b，它可以转变x^2+2ax+b，在进行函数比较时，都有x^2，则可以转变为直线的比较，
对于直线，同样满足凸包性质
如题目[JSOI2008]Blue Mary开公司，可以像本题一样，使用排序+单调栈
当然如果修改为线段，李超树大法好，https://i.cnblogs.com/PostDone.aspx?postid=11156309&actiontip=%e4%bf%9d%e5%ad%98%e4%bf%ae%e6%94%b9%e6%88%90%e5%8a%9f
https://nanti.jisuanke.com/t/39458代码
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cstring> 4 #include <string> 5 #include <cmath> 6 #include <algorithm> 7 #include <iostream> 8 using namespace std; 9 #define ll long long 10 11 const int maxn=1e6+10; 12 const double eps=1e-8; 13 14 ll a[maxn],b[maxn],c[maxn],d[maxn]; 15 int u[maxn]; 16 double v[maxn]; 17 18 double cal(int i,int j) 19 { 20 return (c[i]+c[j]+1.0*(d[i]-d[j])/(c[i]-c[j]))/2; 21 } 22 23 int main() 24 { 25 bool vis=0; 26 int n,m=0,q,i,g; 27 ll r,y; 28 double x; 29 scanf("%d",&n); 30 for (i=1;i<=n;i++) 31 scanf("%lld",&a[i]); 32 for (i=1;i<=n;i++) 33 scanf("%lld",&b[i]); 34 35 a[n+1]=a[n]+1; 36 r=1e18; 37 for (i=1;i<=n;i++) 38 { 39 r=min(r,b[i]); 40 if (a[i]!=a[i+1]) 41 { 42 c[++m]=a[i]; 43 d[m]=r; 44 r=1e18; 45 } 46 } 47 48 g=0; 49 for (i=1;i<=m;i++) 50 { 51 while (g>=2 && cal(i,u[g])<v[g]) 52 g--; 53 54 g++; 55 u[g]=i; 56 if (g>=2) 57 v[g]=cal(u[g],u[g-1]); 58 } 59 60 // for (i=1;i<=g;i++) 61 // printf("%d %.5f ",u[i],v[i]); 62 63 i=2; 64 scanf("%d",&q); 65 while (q--) 66 { 67 scanf("%lf",&x); 68 while (i!=g+1 && v[i]<x) 69 i++; 70 if (!vis) 71 vis=1; 72 else 73 printf(" "); 74 y=(ll)x; 75 printf("%lld",(y-c[u[i-1]])*(y-c[u[i-1]])+d[u[i-1]]); 76 } 77 return 0; 78 } 79 /* 80 3 81 1 3 5 82 0 1 2 83 9 84 -1000000 -1 0 1 2 3 4 5 1000000 85 1000002000001 4 1 0 1 1 2 2 999990000027 86 87 3 88 1 3 5 89 0 1 -10 90 9 91 -1000000 -1 0 1 2 3 4 5 1000000 92 93 4 94 1 1 2 2 95 0 -3 1000 -5 96 5 97 1 2 3 4 5 98 -4 -5 -4 -1 4 99 */