贪心 Codeforces Round #173 (Div. 2) B. Painting Eggs

 1 /*
 2     题意：给出一种方案使得abs (A - G) <= 500，否则输出-1
 3     贪心：每次选取使他们相差最小的，然而并没有-1:)
 4 */
 5 #include <cstdio>
 6 #include <cstring>
 7 #include <iostream>
 8 #include <cmath>
 9 #include <algorithm>
10 using namespace std;
11 
12 const int MAXN = 1e6 + 10;
13 const int INF = 0x3f3f3f3f;
14 
15 int main(void)        //Codeforces Round #173 (Div. 2) B. Painting Eggs
16 {
17 //    freopen ("B.in", "r", stdin);
18 
19     int n;
20     while (scanf ("%d", &n) == 1)
21     {
22         string ans = "";    int sum_a = 0, sum_g = 0;
23         for (int i=1; i<=n; ++i)
24         {
25             int x, y;
26             scanf ("%d%d", &x, &y);
27             if (abs (sum_a + x - sum_g) <= abs (sum_g + y - sum_a))    {ans += "A";    sum_a += x;}
28             else    {ans += 'G';    sum_g += y;}
29         }
30 
31         cout << ans << endl;
32     }
33 
34     return 0;
35 }
编译人生，运行世界！