震惊！！！同一份代码居然跑出两个结果，简直活到爆
- 2020 年 10 月 20 日
- 筆記
\(\Huge 震惊！！！同一份代码居然跑出两个结果，\)
\(\Huge 简直活到爆，这究竟是什么情况呢，快和小编来一探究竟吧\)
在比赛结束后，小编发现自己自己的第二题在题库里的得分是有95分的
但是 \(lemon\) 上却显示小编只有 \(70\) 分
于是小编又在题库中用 \(C++(NOI)\) 的选项交了一次，发现挂成了 \(70\) 分
但是用其它选项去交都是有 \(95\) 分
以上是小编多次测试的结果
下面是小编的源代码
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define rg register
typedef double db;
const int maxn=1e5+15,maxk=24;
int n,k,q[maxn],head,tail;
db a[maxn],f[maxn][maxk];
db getX(int id){
return a[id+1];
}
db getY(int now,int id){
return (double)(f[id][now-1]+a[id+1]*a[id+1]);
}
db xl(int i,int j,int now){
if(getX(i)==getX(j)){
if(getY(now,i)<=getY(now,j)) return 1e18;
else return -1e18;
}
return (getY(now,i)-getY(now,j))/(getX(i)-getX(j));
}
int main(){
freopen("queue.in","r",stdin);
freopen("queue.out","w",stdout);
scanf("%d%d",&n,&k);
for(rg int i=1;i<=n;i++){
scanf("%lf",&a[i]);
}
if(n<=k){
printf("0.0\n");
return 0;
}
std::sort(a+1,a+1+n);
f[0][0]=0;
for(rg int i=1;i<=n;i++){
f[i][1]=(a[i]-a[1])*(a[i]-a[1]);
}
for(rg int i=1;i<=k;i++){
for(rg int j=1;j<i;j++){
f[j][i]=1e9;
}
}
for(rg int t=2;t<=k;t++){
memset(q,0,sizeof(q));
head=1,tail=0;
for(rg int i=1;i<=n;i++){
while(head<tail && xl(q[head],q[head+1],t)<2.0*a[i]) head++;
if(head<=tail) f[i][t]=f[q[head]][t-1]+(a[i]-a[q[head]+1])*(a[i]-a[q[head]+1]);
while(head<=tail && xl(q[tail],i,t)<=xl(q[tail-1],i,t)) tail--;
if(i>=t-1) q[++tail]=i;
}
}
printf("%.2f\n",f[n][k]);
return 0;
}
