美【牛客tracker 每日一题】

美时间限制1秒 空间限制256M知识点枚举网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述最后S ε l ι н α ( S e l i n a ) Sεlιнα(Selina)Sεlιнα(Selina)开始了选美大赛。 一如既往地S ε l ι н α SεlιнαSεlιнα想最大化自己的愉悦度。她品味十分独特对“美”有自己独到的见解。 她给每位经过层层选拔来到这一关的参赛男友都定义了一个帅气值R RR。S ε l ι н α SεlιнαSεlιнα需要将这些参赛者排成一排她对于这个排列的“美”值的定义是其中R i R_iRi​表示排列中第i ii个人的帅气值。特别地当i 1 i1i1时有R i − 1 R n R_{i−1}R_nRi−1​Rn​。她依旧想使自己获得最大的愉悦值所以她要使这个排列的B e A u T i F u L BeAuTiFuLBeAuTiFuL值尽可能地大。聪明的你快来告诉S ε l ι н α SεlιнαSεlιнα这个最大的值是多少。输入描述第一行一个整数N NN表示有N NN个男友。第二行N NN个整数第i ii个数表示值R i R_iRi​。输出描述输出共一行一个整数表示最大的B e A u T i F u L BeAuTiFuLBeAuTiFuL值。示例1输入5 7 3 15 12 8输出34示例2输入7 -2 0 8 9 -5 3 10输出68备注2 ≤ N ≤ 10 5 2≤N≤10^52≤N≤1050 ≤ ∣ R i ∣ ≤ 10 8 0≤∣R_i∣≤10^80≤∣Ri​∣≤108解题思路本题核心是贪心构造最大差值排列求解环形数组相邻元素绝对差之和的最大值。根据贪心结论将数组升序排序后采用最小值与最大值交替排列的策略能让相邻元素的绝对差之和达到最大。使用双指针法左指针指向当前最小值右指针指向当前最大值交替累加两者的差值直到指针相遇。由于题目是环形排列首尾元素会自动形成最大差值无需额外处理。算法的主要耗时为排序操作时间复杂度O ( n log ⁡ n ) O(n\log n)O(nlogn)线性遍历的构造过程效率极高完美适配n ≤ 10 5 n \le 10^5n≤105的数据约束。总结核心逻辑排序后大小交替排列最大化相邻元素绝对差之和环形结构自动补齐首尾差值。关键操作数组升序排序、双指针交替取值、累加差值计算最大值。效率保障排序线性遍历无冗余运算轻松处理十万级数据规模。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll n;cinn;vectorlla(n);for(ll i0;in;i)cina[i];sort(a.begin(),a.end());ll mpn-1,mi0;ll ans0;for(ll i1;mpmi;i1-i){ansa[mp]-a[mi];if(i)mp--;elsemi;}coutansa[n-1]-a[mp]endl;return0;}