记录编号	590709	评测结果	AAAAWWWWWWW
题目名称	(USACO Dec18)平衡木	最终得分	36
用户昵称	flyfree	是否通过	未通过
代码语言	C++	运行时间	2.091 s
提交时间	2024-07-10 17:38:23	内存使用	4.24 MiB

#include<bits/stdc++.h>
using namespace std;
#define MAXN 100010
#define ll long long
ll a[MAXN],s[MAXN];
ll idx,cnt,n;
deque <int> q;
int main(){
    freopen("balance_beam.in","r",stdin);
    freopen("balance_beam.out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i]*=100000;
    }
    q.push_back(0);
    q.push_back(1);
    for(int i=2;i<=n;i++){
        int a1=q.back();
        q.pop_back();
        int a2=q.back();
//        cout<<(a[i]-a[a1])/(i-a1)<<" "<<(a[a1]-a[a2])/(a1-a2)<<endl;
        if((a[i]-a[a1])/(i-a1)<(a[a1]-a[a2])/(a1-a2))q.push_back(a1);
        q.push_back(i);
    }
    while(!q.empty()){
        s[cnt++]=q.front();
        q.pop_front();
//        cout<<s[cnt-1]<<endl;
    }
    s[cnt]=n+1;
    for(int i=1;i<=n;i++){
//        cout<<i<<endl;
        if(i==s[idx+1]){
            cout<<a[i]<<endl;
            idx++;
        }else{
//            cout<<a[s[idx]]<<" "<<(a[s[idx+1]]-a[s[idx]])<<" "<<(s[idx+1]-s[idx])<<" "<<(i-s[idx])<<" ";
            cout<<a[s[idx]]+(a[s[idx+1]]-a[s[idx]])/(s[idx+1]-s[idx])*(i-s[idx])<<endl;
        }
    }
    return 0;
}