首页 > 代码库 > UVa 11039 (排序+贪心) Building designing
UVa 11039 (排序+贪心) Building designing
白书上的例题比较难，认真理解样例代码有助于提高自己
后面的练习题相对简单，独立思考解决问题，增强信心
题意：n个绝对值各不相同的非0整数，选出尽量多的数排成序列，使得该序列正负交错且绝对值递增。
解法：先按绝对值从小到大排序，然后第一个数先入队，然后依次比较后面的数，如果和队尾的数符号相反则入队，直到所有的数遍历完为止
这里用了异或运算，因为这里面没有0，所谓符号相同的两个数异或值为正，不同符号的数异或值为负
1 //#define LOCAL 2 #include <algorithm> 3 #include <cstdio> 4 #include <cstring> 5 #include <cmath> 6 using namespace std; 7 8 const int maxn = 500000 + 10; 9 int a[maxn];10 bool cmp(int a, int b)11 {12 return abs(a) < abs(b);13 }14 15 int main(void)16 {17 #ifdef LOCAL18 freopen("11039in.txt", "r", stdin);19 #endif20 21 int T, n;22 scanf("%d", &T);23 while(T--)24 {25 scanf("%d", &n);26 for(int i = 0; i < n; ++i)27 scanf("%d", &a[i]);28 sort(a, a+n, cmp);29 int q = 0, cnt = 1;30 for(int i = 1; i < n; ++i)31 if((a[i] ^ a[q]) < 0)32 {33 q = i;34 ++cnt;35 }36 printf("%d\n", cnt);37 }38 return 0;39 }
UVa 11039 (排序+贪心) Building designing
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。