题目描述: 给出一个仅包含加减乘除四种运算符的算式(不含括号),如1+2*3/4,在保持运算符顺序不变的情况下,现在你可以进行若干次如下操作:如果交换相邻的两个数,表达式值不变,那么你就可以交换这两个数。
现在你可以进行任意次操作,使得算式的数字序列字典序最小,然后输出结果,数字之间的字典序定义为若a<b则a的字典序小于b。
输入 第一行包含一个整数n,表示算式的长度,即包含n个数字和n-1个运算符。(1≤n≤100000)。
第二行包含一个含有n个非0整数和n-1个运算符的算式,整数与运算符用空格隔开,运算符包括“+,-,*,/”,整数的绝对值不超过1000。
输出 按要求输出字典序最小的表达式,数字与符号之间用空格隔开。
样例输入 6 3 + 2 + 1 + -4 * -5 + 1 样例输出 1 + 2 + 3 + -5 * -4 + 1
思路:参考自
先用两个数组来存储数字(opNum)和这个数字之前的操作符(opChar)。其中ops第一个元素固定是'+',因为第一个数没有符号。例如样例就会得到如下的两个数组:
索引 | 0 | 1 | 2 | 3 | 4 | 5 |
nums | 3 | 2 | 1 | -4 | -5 | 1 |
ops | + | + | + | + | * | + |
接着用两个指针 l 和 r,一段一段地找ops中连续的操作符,例如样例中就会得出“l=0,r=3; l=4,r=4; l=5,r=5”三段。 接着根据一套规则来确定 l 和 r 区间内哪些元素是需要进行排序,以实现字典序最小:
- 如果ops[l]是加号或减号
- 这段区间下一个操作符是'*'或者‘/’,那么要排序的区间是[l, r-1]; 想想类似5+4+3+2+1*5的情况
- 这段区间下一个操作符是'-',那么要排序的区间是[l, r];想想类似5+4+3+2+1-5的情况
- 这里不需要考虑区间前一个操作符是*、/,-,要排序的区间肯定是[l, r],可参考5*4+1+2+3的情况 (故2,3归为else语句即可)
- ops[l]是乘号
- 区间前一个操作符是'+'或者‘-’,那么要排序的区间是[l-1, r];想想类似1+5*4*3*2*1的情况
- 区间前一个操作符是‘/’,那么要排序的区间是[l, r];想想类似1/5*4*3*2*1的情况
- ops[l]是除号
- 不论什么情况,要排序的区间都是[l, r];
#include<iostream> #include<vector> #include<string> #include<algorithm> using namespace std; int Partition(vector<int> &nums, int l, int r){ int pivot = nums[l]; while(l<r){ while(l<r && pivot<=nums[r]) --r; nums[l] = nums[r]; while(l<r && pivot>=nums[l]) ++l; nums[r] = nums[l]; } nums[l] = pivot; return l; } void QuickSort(vector<int> &nums, int l, int r){ if(l<r){ int mid = Partition(nums, l, r); QuickSort(nums, l, mid-1); QuickSort(nums, mid+1, r); } } int main() { int n; cin>>n; vector<int> opNum(n, 0); vector<char> opChar(n, '+'); for(int i=0;i<n-1;i++){ cin>>opNum[i]; cin>>opChar[i+1]; } cin>>opNum[n-1]; int l=0, r=0; while(r<n){ while( r<n && opChar[l]==opChar[r]){ r++; } r--; //cout<<l<<" "<<r<<endl; if(opChar[l]=='*' ){ if(l-1>=0 && (opChar[l-1]=='+' || opChar[l-1]=='-')) QuickSort(opNum, l-1, r); else QuickSort(opNum, l, r); }else if(opChar[l]=='+' || opChar[l]=='-'){ if(r+1<n-1 && (opChar[r+1]=='*' || opChar[r+1]=='|')) QuickSort(opNum, l, r-1); else QuickSort(opNum, l, r); }else if(opChar[l]=='/'){ QuickSort(opNum, l, r); } r++; l = r; } for(int i=0;i<n-1;i++){ cout<<opNum[i]<<" "; cout<<opChar[i+1]<<" "; } cout<<opNum[n-1]<<endl; return 0; //3 + 2 + 1 + -4 * -5 + 1 ---> 1 + 2 + 3 + -5 * -4 + 1 }