CF div2 E. Water Balance

给你n个数，你可以这样操作：使区间[l,r]的数变成他们的平均数，求字典序最小的序列。

做法：从左往右逐个比较，比较完之后会形成一个区间，一开始是区间为1的数进行比较，到后来会

变成区间较大的进行比较；

举个例子：7 6 5 4 3 2 3

显而易见，递减序列肯定是要求平均值的，但是求出来之后，会得出一个值，这个值有可能大于或小于等于右边的数

这就需要再次进行比较，所以每次比较都是以区间的形式；

代码中区间为block

 #include<bits/stdc++.h>

 #define IOS ios::sync_with_stdio(false);cin.tie(0)

 #define ll long long

 //#define ll unsigned long long

 #define R register int

 #define inf 0x3f3f3f3f

 #define mod 1000000007

 #define eps 1e-6

 #define pi acos(-1)

 #define mea (memset(a,0,sizeof(a)))

 #define myit set<ll>::iterator

 #define myits  multiset<ll>::iterator

 #define v30 (1<<30)-1

 #define all(x) (x).begin(),(x).end()

 #define maxs *s.rbegin()

 #define fi first

 #define se second

 using namespace std;

 inline ll read(){

    ll s=,w=;

    char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')w=-;ch=getchar();}

    while(ch>=''&&ch<='') s=s*+ch-'',ch=getchar();

    return s*w;

 }

 void put1(){ puts("YES") ;}

 void put2(){ puts("NO") ;}

 void put3(){ puts("-1"); }

 ll gcd(ll a,ll b){ return b==?a:gcd(b,a%b);}

 using namespace std;

 const int manx=2e6+;

 double water[manx]; //水

 double block[manx]; //区间块的长度

 double ans[manx]; //答案

 int main()

 {

     ll n = read();

     for ( int i=; i<=n ;i++)

         scanf("%lf",&water[i]);

     ll l = ;

     for ( int i= ; i<=n ;i++){

         ans[++l] = water[i];

         block[l] = ;

         while ( l> && ans[l] < ans[l-]){

             ans[l-]=( ans[l-]* block[l-] + ans[l] * block[l])

             / ( block[l] + block[l-]);

             block[l-] += block[l];

             --l;

         }

     }

     for ( int i= ; i<=l ;i++)

         for ( int j= ; j<= block[i]; j++)

             printf("%.9lf\n",ans[i] );

     return ;

 }

巴特西

CF div2 E. Water Balance

最新文章

热门文章