首页 > 代码库 > ZOJ3798 Abs Problem
ZOJ3798 Abs Problem
题目：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3798
学会了对于序列用next_permutation暴力打表
可以先打表找规律
#include<cstdio>#include<algorithm>#define INF 0x3f3f3f3f//#define N 100using namespace std;int seq[N];//保存当前序列int mi[N], ma[N];//保存最小值最大值相应序列int calc(int n)//总排序数{ int p = 1; for (int i = 1; i <= n; ++i) p *= i; return p;}int main(){ int n; while (~scanf("%d", &n)) { for (int i = 1; i <= n; ++i) seq[i] = i; int k = calc(n), MIN = INF, MAX = -INF; for (int i = 0; i < k; ++i) { int b; next_permutation(seq + 1, seq + n + 1); for (int i = 1; i <= n; ++i) { if (i == 1) b = seq[i]; else b = abs(b - seq[i]); } if (b <= MIN) { MIN = b; for (int i = 1; i <= n; ++i) mi[i] = seq[i]; } if (b>=MAX) { MAX = b; for (int i = 1; i <= n; ++i) ma[i] = seq[i]; } } printf("%d %d\n", MIN, MAX); for (int j = 1; j <= n; ++j) printf("%d ", mi[j]); puts(""); for (int j = 1; j <= n; ++j) printf("%d ", ma[j]); puts(""); } return 0;}
规律：逆序时最小，将逆序最大放到末位时最大
n%4==3或0时，最小值为0，其余都为1
举个例子：序列7 6 5 4 3 2 1
此时该序列为最小值，会发现：从7开始每4个数的绝对值为0，每两个数为1，所以若n%4==3时，剩下的最后3个为3 2 1，易得最小值为0，n%4==0、1、2时同理。
最大值MAX(n)=n-MIN(n-1)
AC代码：
1 #include<cstdio> 2 #define N 50005 3 int getMin(int n) 4 { 5 if (n % 4 == 3 || n % 4 == 0) 6 return 0; 7 return 1; 8 } 9 int main()10 {11 int n;12 while (~scanf("%d", &n))13 {14 printf("%d %d\n", getMin(n), n - getMin(n - 1));15 for (int i = n; i > 0; --i)16 {17 if (i > 1)printf("%d ", i);18 else printf("%d\n", i);19 }20 for (int i = n-1; i > 0; --i)21 printf("%d ", i);22 printf("%d\n", n);23 }24 return 0;25 }
ZOJ3798 Abs Problem
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。