温州知名网站,网页设计简单,创意品牌型网站,网站建设维护升级文章目录 [Dual (Hard Version)](https://codeforces.com/contest/1855/problem/C2)问题建模问题分析1.按元素值分类讨论#xff0c;正负不同时存在时2.若正负同时存在时代码 Dual (Hard Version) 问题建模
给定n个数#xff0c;n不超过20#xff0c;且每个数ai#xff0c… 文章目录 [Dual (Hard Version)](https://codeforces.com/contest/1855/problem/C2)问题建模问题分析1.按元素值分类讨论正负不同时存在时2.若正负同时存在时代码 Dual (Hard Version) 问题建模
给定n个数n不超过20且每个数ai − 20 a i 20 -20ai20 −20ai20可以执行多次操作每次可以选择两个数aiaj使得aiaiaj需要在31次操作内使得元素为非降序排列并输出操作数和操作使选取的ij。
问题分析
1.按元素值分类讨论正负不同时存在时
若元素值都为大于等于0时对于每一个比前一个元素小的元素加上前面元素后就会变成所需的大小关系操作最多为19次。
若元素值都为小于等于0时对于每一个比前一个元素小的元素让前面的元素加上当前元素即可变成所需的大小关系操作最多为19次。
2.若正负同时存在时
若正负数都有则可以将负数变成正的或者正数变为负的变为上面两种情况之一由于转换为上面两种情况后最多需要19次操作才能使得最终元素排列为所需则最多有12次操作可以将当前情况变为上述两种情况之一。
由于改变元素正负需要通过最大正数或者负数来进行则从绝对值最大的正负性的情况来分析。
若绝对值最大的数为正数则考虑将负数都变为正数若负数的个数不超过12时可以完成。
若超过12个则只能考虑将正数都变为负数由于负数个数超过12则正数最多只有7个数则可以考虑使用5次操作获得一个比所有正数绝对值大的负数然后再将7个正数变为负数由于i,j选择同一个数时等价2乘该数则选择5次有2^5负数绝对值最小的数为-15次操作后为-32其绝对值大于最大的正数故可以在12次内将将正数变为负数。绝对值最大为负数同理
所以最终有解的情况为取将所有元素变为大于等于0的数所需操作以及将所有元素变为小于等于0的数所需操作的最小操作数的操作方案。
代码
#includebits/stdc.h#define x first
#define y second
#define C(i) str[0][i]!str[1][i]
using namespace std;
typedef unsigned long long ULL;
typedef long long LL;
typedef pairint, int PII;
typedef pairLL, LL PLL;
const int N 30, Mod 998244353, P 2048;
int a[N];void solve() {int n;cin n;///正负数个数以及正负数中绝对值最大的元素的下标起始时对应元素为0int pcnt0,ncnt0,minp0,maxp0;for(int i1;in;i){cin a[i];if(a[i]0){pcnt;if(a[i]a[maxp]) maxpi;}else if(a[i]0){ncnt;if(abs(a[i])abs(a[minp])) minpi;}}if(pcnt0ncnt0){cout 0endl;}else {int x10,y10;///记录获得正数绝对值最大和负数绝对值最大所需的操作数if(abs(a[maxp])abs(a[minp])) y15;else x15;//采用变正和变负中操作数最小的操作方案if(x1ncnty1pcnt){cout x1ncntn-1\n;for(int i0;ix1;i) cout maxp maxp\n;for(int i1;in;i){if(a[i]0) cout i maxp \n;}for(int i1;in;i) cout i1 i \n;}else{cout y1pcntn-1 \n;for(int i0;iy1;i) cout minp minp\n;for(int i1;in;i){if(a[i]0) cout i minp \n;}for(int in;i1;i--) cout i-1 i \n;}}
}int main() {int t 1;cin t;while (t--) solve();return 0;
}
