为网站 做字幕,相册网站模板,河北信息门户网站定制,网站怎么做弹出表单灵能传输
友情链接#xff1a;灵能传输
题目#xff1a; 输入样例#xff1a; 3
3
5 -2 3
4
0 0 0 0
3
1 2 3输出样例#xff1a; 3
0
3思路#xff1a;
题目大意#xff1a;给出一个数组#xff0c;每次选择数组中的一个数#xff08;要求不能是第一个数与最后一个…灵能传输
友情链接灵能传输
题目 输入样例 3
3
5 -2 3
4
0 0 0 0
3
1 2 3输出样例 3
0
3思路
题目大意给出一个数组每次选择数组中的一个数要求不能是第一个数与最后一个数如果这个数是一个正数就将这个数减去自身两次并且将相邻的两个数分别加上这个数一次如果这个数是负数就将这个数减去自身两次并且将相邻的数加上这个负数两次本质上第二种情况与第一种情况一样因为减去负数相当于加上这个负数的绝对值使用公式表述为 a i − 1 a i a i 1 a i a i − 2 a i a_{i - 1} a_i ~~~~~~~~ a_{i 1} a_i~~~~~~~~a_i - 2a_i ai−1ai ai1ai ai−2ai并且记住选择的i不能是第一个数或最后一个数。
具体思路
通过尝试可知公式与每一个数的前缀和有极大的关系举例对于数组5 -2 3 4而言其前缀和为5 3 6 10如果选择的是-2那么原数组的值会变为3 2 1 4变化后的数组前缀和为3 5 6 10相当于将原数组的前缀和中的第一个位置与第二个位置进行了交换再看还是对于数组5 -2 3 4而言如果选择的是3那么原数组的值会变为5 1 -3 7对应的前缀和为5 6 3 10相当于对原数组的前缀和数组的第二个位置与第三个位置进行了交换。下图为更直观的理解 由此我们可以得出一个规律如果对某一个位置i进行操作相当于对前缀和数组中i与i - 1位置的值进行交换。其中1 i n。
这样我们就可以得出一个简单的解决方案了题目要求的是使原数组中数值的绝对值的最大值最小化一个简单的思路是对前缀和数组进行排序因为这样可以保证相邻两个前缀和数值的差值最小这样就保证了原数组中的数值的最大值最小化。
但是题目还有一个条件就是不能对第一个位置和最后一个位置进行操作如果直接对前缀和数组前缀和数组表示为 S S S进行排序包含了 S 0 S_0 S0和 S n S_n Sn那么就违反了题目的要求。我们这样思考如果对 a 1 a_1 a1原数组用 a a a表示进行操作那么对应的前缀和变化是交换 S 0 S_0 S0和 S 1 S_1 S1其中 S 0 0 S_0 0 S00 如果对 a n a_n an进行操作那么对应的前缀和数组的变化是交换 S n S_n Sn和 S n − 1 S_{n - 1} Sn−1为了不使 S 0 S_0 S0和 S n S_n Sn移动我们这两个数进行移动我们需要让起点仍然是因为 S 0 S_0 S0和 S n S_n Sn但为了使相邻两个值之间的差值最小我们需要使用一些策略如从 S 0 S_0 S0的位置进行步长为2向前进行取值正序填充到一个新的数组中去并且进行标记在 S n S_n Sn的位置也进行步长为2向后进行取值逆序即从新数组的最后一个位置开始进行填充填充到一个新的数组中去并且进行标记最后从头开始遍历排序后的前缀和数组将还未标记的值按顺序一次填充到新的数组的空余位置。
还有一个问题 S 0 S_0 S0如果大于 S n S_n Sn该如何解决
对于这种情况我们只需要在查找 S 0 S_0 S0和 S n S_n Sn的位置的时候将 S 0 S_0 S0和 S n S_n Sn的位置进行交换即可这样就变为了 S n S_n Sn向前进行步长为2的取值 S 0 S_0 S0向后进行步长为2的移动。下图为一个直观的理解
记得要使用long long数据类型因为int类型的数据最大在 1 0 9 10^9 109左右而题目要求的 a i a_i ai的值小于等于 1 0 9 10^9 109其前缀和数组的值可能会超过int的存储容量。
代码
#includebits/stdc.h
using namespace std;typedef long long ll;
void solve(){int n; cinn;vectorll A(n 1, 0);vectorll S(n 1, 0);for(int i 1;i n;i ){cinA[i];S[i] S[i - 1] A[i];}// 记录S中的第一个位置与最后一个位置ll front S[0];ll end S[n];if(front end) swap(front, end);// 对前缀和数组进行顺序排序sort(S.begin(), S.end()); // 排序的时候包含了第0个位置的数 // 找到原来S数组的第一个位置和最后一个位置的数在排序后的数组中的下标for(int i 0;i n;i ){if(S[i] front){front i;break;}}for(int i n;i 0;i --){ // 这里遍历也可以从0开始到n结束if(S[i] end){end i;break;}}vectorll ans(n 1, 0);// 设定标记数组vectorll cnt(n 1, 0);ll frontidx 0;ll endidx n; // 从idxf向前进行找for(int i front;i 0;i - 2){ans[frontidx] S[i];cnt[i] 1;}// 从idxe向后进行找 for(int i end;i n ;i 2){ans[endidx --] S[i];cnt[i] 1;}// 将剩下的数进行填充 for(int i 0;i n;i ){if(!cnt[i]){ans[frontidx] S[i];}}// 从ans数组中找到相邻两个数之间的最小的值ll tans 0;for(int i 1;i n;i ){tans max(tans, abs(ans[i] - ans[i - 1]));}couttansendl;return ;
} signed main(){ios::sync_with_stdio(0);cin.tie(0);int t 1; cint; // t组询问 while(t--){solve();}return 0;
}
