贪心 Codeforces Round #288 (Div. 2) B. Anton and currency you all know

  1 /*
  2     题意：从前面找一个数字和末尾数字调换使得变成偶数且为最大
  3     贪心：考虑两种情况：1. 有偶数且比末尾数字大(flag标记)；2. 有偶数但都比末尾数字小(x位置标记)
  4     仿照别人写的，再看自己的代码发现有清晰的思维是多重要
  5 */
  6 #include <cstdio>
  7 #include <iostream>
  8 #include <algorithm>
  9 #include <cmath>
 10 #include <cstring>
 11 #include <map>
 12 using namespace std;
 13 
 14 const int MAXN = 1e5 + 10;
 15 const int INF = 0x3f3f3f3f;
 16 char s[MAXN];
 17 
 18 int main(void)        //Codeforces Round #288 (Div. 2) B. Anton and currency you all know
 19 {
 20     #ifndef ONLINE_JUDGE
 21         freopen ("B.in", "r", stdin);
 22     #endif
 23 
 24     scanf ("%s", &s);
 25 
 26     int len = strlen (s);
 27     bool flag = false;
 28     int x = -1;
 29     for (int i=0; i<len-1; ++i)
 30     {
 31         if ((s[i] - '0') % 2 == 0)
 32         {
 33             x = i;
 34             if (s[i] < s[len-1])
 35             {
 36                 swap (s[i], s[len-1]);
 37                 flag = true;    break;
 38             }
 39         }
 40     }
 41 
 42     if (!flag)
 43     {
 44         swap (s[x], s[len-1]);
 45     }
 46     (x != -1) ? printf ("%s
", s) : puts ("-1");
 47 
 48     return 0;
 49 }
 50

 1 if (len == 1)
 2     {
 3         puts ("-1");
 4     }
 5     else if (len == 2)
 6     {
 7         if ((s[0] - '0') % 2 != 0)    puts ("-1");
 8         else
 9         {
10             printf ("%c%c
", s[1], s[2]);
11         }
12     }
13     else if (len == 3)
14     {
15         if ((s[1] - '0') % 2 == 0)
16         {
17             if ((s[0] - '0') % 2 == 0)
18             {
19                 if (s[0] > s[1])    swap (s[0], s[2]);
20                 else    swap (s[1], s[2]);
21                 printf ("%s
", s);
22             }
23             else
24             {
25                 swap (s[1], s[2]);
26                 printf ("%s
", s);
27             }
28         }
29         else if ((s[0] - '0') % 2 == 0)
30         {
31             swap (s[0], s[2]);
32             printf ("%s
", s);
33         }
34         else    puts ("-1");
35     }
36     else
37     {
38         char ch = '0';    int x = -1;
39         for (int i=len-2; i>=0; --i)
40         {
41             if ((s[i]-'0') % 2 == 0)
42             {
43                 if (ch <= s[i])
44                 {
45                     if (ch == s[i])
46                     {
47                         if (s[i] < s[len-1])
48                         {
49                             ch = s[i];     x = i;
50                         }
51                     }
52                     else
53                     {
54                         ch = s[i];     x = i;
55                     }
56                 }
57             }
58         }
59         if (x == -1)    puts ("-1");
60         else
61         {
62             swap (s[x], s[len-1]);
63             printf ("%s
", s);
64         }
65     }

思维混乱的代码

编译人生，运行世界！