A. Lala Land and Apple Trees
题目描述：
一条坐标轴，在坐标轴上散布了一些苹果树，每棵树都有位置和所结果实数目两个属性，Amr在坐标轴0点的位置，Amr在开始的时候可以选择向左或者右走，然后遇到果树才能改变方向，问最后最多能拿到多少个苹果？
解题思路：
开两个数组，分别代表坐标正半轴和负半轴，然后对每个数组排下一序，刚开始选择苹果树多的方向，然后累加就好。
1 #include <bits/stdc++.h> 2 using namespace std; 3 struct node 4 { 5 int x, y; 6 }; 7 const int maxn = 110; 8 node x[maxn], y[maxn]; 9 int cmp (const void *a, const void *b) 10 { 11 node *c = (node *)a; 12 node *d = (node *)b; 13 return c->x - d->x; 14 }//按照a[i].x升序排列 15 int main () 16 { 17 int n; 18 while (scanf ("%d", &n) != EOF) 19 { 20 int a, b, i, j; 21 i = j = 0; 22 for (int k=0; k<n; k++) 23 { 24 scanf ("%d %d", &a, &b); 25 if(a < 0) 26 { 27 x[i].x = -a;//注意负数的时候要降序排 28 x[i ++].y = b; 29 } 30 else 31 { 32 y[j].x = a; 33 y[j++].y = b; 34 } 35 } 36 qsort (x, i, sizeof(x[0]), cmp); 37 qsort (y, j, sizeof(y[0]), cmp); 38 if (i < j) 39 j = i + 1; 40 else if (j < i) 41 i = j + 1; 42 int sum = 0; 43 for (int k =0; k<i; k++) 44 sum += x[k].y; 45 for (int k=0; k<j; k++) 46 sum += y[k].y; 47 printf ("%d\n", sum); 48 } 49 return 0; 50 }
B. Amr and The Large Array
题目描述：
给出n个数字，求出在这n个数中用最小的区间包含全部出现次数最多的数，输出此区间下标，如果有多个输出任意一个。
解题思路：
用hash存储，就用不上排序了，并且处理起来也方便，复杂度也低。
1 #include <bits/stdc++.h> 2 using namespace std; 3 struct node 4 { 5 int x, y, z; 6 }; 7 const int maxn = 1000010; 8 node x[maxn];//x[i].x——i出现的数目，x[i].y——i出现的最小下标，x[i].z——i出现的最大下标 9 int main () 10 { 11 int n; 12 while (scanf ("%d", &n) != EOF) 13 { 14 int a, b, Max = 0; 15 memset (x, 0, sizeof(x)); 16 for (int i=1; i<=n; i++) 17 { 18 int num; 19 scanf ("%d", &num); 20 x[num].x++; 21 if (i < x[num].y || x[num].y == 0) 22 x[num].y = i; 23 if (i > x[num].z) 24 x[num].z = i; 25 if (x[num].x > Max || (x[num].x == Max && x[num].z - x[num].y < b - a)) 26 { 27 Max = x[num].x; 28 a = x[num].y; 29 b = x[num].z; 30 } 31 } 32 printf ("%d %d\n", a, b); 33 } 34 return 0; 35 }
未完待续······
Codeforces Round #312 (Div. 2)
原文：http://www.cnblogs.com/alihenaixiao/p/4647300.html
