I:后缀表达式
题目描述
给定 N 个加号、M 个减号以及 N+M+1个整数A1,A2,⋅⋅⋅,AN+M+1，小明想知道在所有由这 NN 个加号、M 个减号以及 N+M+1 个整数凑出的合法的 后缀表达式中，结果最大的是哪一个？
请你输出这个最大的结果。
例如使用 1 2 3 + -，则 "2 3 + 1 -" 这个后缀表达式结果是 4，是最大的。
输入描述
第一行包含两个整数 N,M。
第二行包含 N+M+1 个整数 A1,A2,⋅⋅⋅,AN+M+1。
其中，0≤N,M≤105，−10的9次方≤Ai≤10的9次方。
输出描述
输出一个整，代表答案。
输入输出样例
示例
输入
1 1 1 2 3
输出
4
运行限制
最大运行时间：1s
最大运行内存: 256M
首先要知道什么是后缀表达式，后缀表达式和四则运算不同，以这道题为例：
2 3 + 1 -
2进栈，3进栈，此时栈为 3 2
然后下一个是“+”，此时将2,3去除，先取出3放右边，再取出2放左边，变为2+3=5，然后5进栈；
此时栈里只有5，然后1进栈此时栈为 1 5，下一个为-，将1取出放右边，5取出放左边5-1=4；
答案为4，后缀表达式可不是四则运算，这道题容易误以为排序后将大的加起来，减去小的。
例如；3+2-1=4；这只是巧合；
注意先出栈的在符号右边
再说这道题的思路，首先分为三部分，所有数大于0，所有数小于0和有正负三种，然后考虑有无减号，逐个分析。
#include <iostream> #include <algorithm> using namespace std; int n,m; long long a[1000000]; long long sum; long long ans; int main(){ cin>>n>>m; for(int i=0;i<=m+n;i++){ cin>>a[i]; sum+=a[i]; } sort(a,a+n+m+1); if(a[0]>=0){ if(m){ //所有数大于0 ans=sum-a[0]*2; //有减号时 cout<<ans; return 0; }else{ cout<<sum; //没有减号 return 0; } } if(a[n+m]<=0){ sum=sum*-1+2*a[n+m]; //都是负数时 cout<<sum; return 0; } if(m==0){ cout<<sum; return 0; } for(int i=0;i<=n+m&&a[i]<0;i++){ //有正数和负数时分为有无减号。 sum-=a[i]*2; } cout<<sum; return 0; }
J：灵传输能
题目描述
题目背景
在游戏《星际争霸 II》中，高阶圣堂武士作为星灵的重要 AOE 单位，在 游戏的中后期发挥着重要的作用，其技能"灵能风暴"可以消耗大量的灵能对 一片区域内的敌军造成毁灭性的伤害。经常用于对抗人类的生化部队和虫族的 刺蛇飞龙等低血量单位。
问题描述
你控制着 nn 名高阶圣堂武士，方便起见标为 1,2,··· ,n1,2,⋅⋅⋅,n。每名高阶圣堂武士需要一定的灵能来战斗，每个人有一个灵能值 ai 表示其拥有的灵能的多少，a_iai非负表示这名高阶圣堂武士比在最佳状态下多余了 ai 点灵能，ai 为负则表示这名高阶圣堂武士还需要 ai 点灵能才能到达最佳战斗状态）。
现在系统赋予了你的高阶圣堂武士一个能力，传递灵能，每次你可以选择一个 i∈[2,n−1]，若 ai ≥ 0 则其两旁的高阶圣堂武士，也就是 i−1、i+1 这两名高阶圣堂武士会从 i 这名高阶圣堂武士这里各抽取 ai 点灵能；若ai < 0 则其两旁的高阶圣堂武士，也就是 i−1,i+1 这两名高阶圣堂武士会给 i 这名高阶圣堂武士 ai 点灵能。形 式化来讲就是 ai−1+=ai,ai+1+=ai,ai−=2ai。
灵能是非常高效的作战工具，同时也非常危险且不稳定，一位高阶圣堂武士拥有的灵能过多或者过少都不好，定义一组高阶圣堂武士的不稳定度为 所有灵能取绝对值的最大值，请你通过不限次数的传递灵能操作使得你控制的这一组高阶圣堂武士的不稳定度最小。
输入描述
本题包含多组询问。
输入的第一行包含一个正整数 TT 表示询问组数。 接下来依次输入每一组询问。
每组询问的第一行包含一个正整数 nn，表示高阶圣堂武士的数量。
接下来一行包含 n 个数 a1,a2,⋅⋅⋅,an。
其中，T≤3，3≤n≤300000，∣ai∣≤10的九次方.
输出描述
输出 TT 行。每行一个整数依次表示每组询问的答案。
输入输出样例
示例
输入
3 3 5 -2 3 4 0 0 0 0 3 1 2 3
输出
3 0 3
运行限制
最大运行时间：1s
最大运行内存: 256M
一维前n项和问题，难点在于寻找点的排列方法，求前n项和，也就是前缀和，除了s[0]和s[n];不能动外其余任意排列，使得每两项差值的绝对值最小。说白了，就是固定起点和终点，给一些固定的点，使得这条曲线的斜率的绝对值最小。输出最小值就好了
具体推理过程请点我
#include <iostream> #include <algorithm> #include <cstring> using namespace std; int t; long long sum[300005]; long long ans[300005]; int a[300005]; bool v[300005]; int n; int max(int x,int y){ if(x>=y){ return x; } return y; } int main(){ cin>>t; for(int i=0;i<t;i++){ memset(v,false,300005); //清空，因为要重复用 cin>>n; sum[0]=0; for(int j=1;j<=n;j++){ cin>>a[j]; sum[j]=sum[j-1]+a[j]; //前n项和 } if(sum[0]>sum[n]){ long long f=sum[n]; sum[n]=sum[0]; //使sum[0]是小端 sum[0]=f; } long long s0=sum[0]; long long sn=sum[n]; sort(sum,sum+n+1); int s0w,snw; //排序，s[0]和s[n],不变 位于两边 for(int j=0;j<=n;j++){ if(sum[j]==s0){ s0w=j; break; } } for(int j=0;j<=n;j++){ if(sum[j]==sn){ snw=j; break; } } int l=0; int r=n; for(int j=s0w;j>=0;j-=2){ ans[l]=sum[j]; //从sow开始，往小的部分遍历，各两个取一个 l++; v[j]=1; //标记已经填过 } for(int j=snw;j<=n;j+=2){ ans[r]=sum[j]; //从snw开始，往大的部分遍历，隔两个取一个 r--; v[j]=1; } for(int j=0;j<=n;j++){ if(!v[j]){ //没有进入的按照大小顺序进入 ans[l]=sum[j]; //r--注意，放到snw前面 l++; } } int ansz=-1; //取一个答案不可能的变量作为答案的载体 for(int j=1;j<=n;j++){ ansz=max(ansz,abs(ans[j]-ans[j-1])); } cout<<ansz<<endl; } return 0; }
