Codeforces Round #839 (Div. 3) D. Absolute Sorting

悠悠 2024-03-30 12:37 77阅读 0赞

[Problem - D - Codeforces][]

题意：

给定一个数列，让你选定一个 x ，然后让所有数都变成 abs(a\[i\]-x)，问你 x 取多少可以使该数列变成不严格递增

思路：

这道题，利用了一个性质

对于两个数 a,b

当x的值小于 (a+b)/2 时，它保持原本的单调性

当x的值等于(a+b)/2时，a==b

当x的值大于(a+b)/2时，单调性反一下

因此，如果遇到升序的，x就得小于(a+b)/2，即x属于 \[-inf,(a+b)/2\]

遇到降序的，x就得大于(a+b)/2+1，即x属于 \[(a+b)/2+1,inf\]

然后把这些区间取个交集就好了

Code：

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    const int mxn=2e5+10,mnf=1e18;
    int n,l,r;
    int a[mxn];
    void solve(){
    	l=0,r=mnf;
    	cin>>n;
    	for(int i=1;i<=n;i++) cin>>a[i];
    	for(int i=2;i<=n;i++){
    		int x=0,y=mnf; 
    		if(a[i]>a[i-1]) y=(a[i]+a[i-1])/2;
    		else if(a[i]<a[i-1]) x=(a[i]+a[i-1]+1)/2;
    		l=max(l,x),r=min(r,y);
    	}
    	if(l>r) cout<<-1<<'\n';
    	else cout<<l<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;cin>>__;
    	while(__--)solve();return 0;
    }

**总结：**

**总结一个性质：**

**对于两个数 a,b，使它们变成abs(a-x)，abs(b-x)**

**当x的值小于 (a+b)/2 时，它保持原本的单调性**

**当x的值等于(a+b)/2时，a==b**

**当x的值大于(a+b)/2时，单调性反一下**

[Problem - D - Codeforces]: https://codeforces.com/contest/1772/problem/D

发表评论取消回复

表情：

评论列表（有 0 条评论，77人围观）

还没有评论，来说两句吧...

相关阅读

相关 Codeforces Round #834 (Div. 3) D. Make It Round

[Problem - D - Codeforces][] ![1c21641e1301413ea5db4b38f928ab5a.png][] Code： incl

￡神魔★判官ぃ/ 2024年03月31日 13:51/ 0 赞/ 84 阅读

相关 Codeforces Round #839 (Div. 3) C. Different Differences

[Problem - C - Codeforces][] 题意：给定n和k，让你构造一个长度为k的数列，使其差分数组的数的种类尽可能多思路：贪心+构造种类尽可

迷南。/ 2024年03月30日 12:37/ 0 赞/ 69 阅读

相关 Codeforces Round #839 (Div. 3) D. Absolute Sorting

[Problem - D - Codeforces][] 题意：给定一个数列，让你选定一个 x ，然后让所有数都变成 abs(a\[i\]-x)，问你 x 取多少可以使该

悠悠/ 2024年03月30日 12:37/ 0 赞/ 78 阅读

相关 Codeforces Round #839 (Div. 3) E Permutation Game

[Problem - E - Codeforces][] 题意：给定一个排列，两个人博弈，每次他可以给所有涂蓝的块排序，然后把一个红的染成蓝色。先手想把数列排成升序，后手

喜欢ヅ旅行/ 2024年03月30日 12:37/ 0 赞/ 73 阅读

相关 Codeforces Round #479 (Div. 3)

D:[Divide by three, multiply by two][Divide by three_ multiply by two] 除了这种做法还可以通过建图

￡神魔★判官ぃ/ 2022年05月24日 20:59/ 0 赞/ 184 阅读

相关 Codeforces Round #506 (Div. 3) D. Concatenated Multiples

题目：[点击打开链接][Link 1] 题意：给你n个数，求任意两个数组合而成能整除k的对数。分析：根据除法的定义暴力就行了，用map或者unordered\_

小鱼儿/ 2022年05月15日 06:35/ 0 赞/ 163 阅读

相关 Codeforces Round #552 (Div. 3)

C. Gourmet Cat 题目：[http://codeforces.com/contest/1154/problem/C][http_codeforces.com_

骑猪看日落/ 2022年04月24日 07:04/ 0 赞/ 160 阅读

相关 Codeforces Round #552 (Div. 3)D、E题解

D. Walking Robot 题意机器人在一维坐标轴上从0走到x，中途可以在有光的地方可以选择给太阳能电池充电，每次移动都要消耗一单位电，蓄电池容量为a，太阳

￡神魔★判官ぃ/ 2022年01月12日 08:19/ 0 赞/ 227 阅读

相关 Codeforces Round #552 (Div. 3)

B. Make Them Equal Description 给定一个长度为 nn 的序列，请你选择一个非负整数 DD，然后将序列中的所有元素要么加上 DD，要么减去

偏执的太偏执、/ 2021年11月10日 12:48/ 0 赞/ 248 阅读

相关 Codeforces Round #560 (Div. 3)

[Codeforces Round \560 (Div. 3)][Codeforces Round _560 _Div. 3] E. Two Arrays and

野性酷女/ 2021年11月01日 04:38/ 0 赞/ 244 阅读