Codeforces Round #249 (Div. 2) A B C
http://codeforces.com/contest/435
代码均已投放：https://github.com/illuz/WayToACM/tree/master/CodeForces/435
435A - Queue on Bus Stop
题目地址
题意：
给出n组人的人数在排队等公交，每辆公交最多坐m人。
一定是按队列顺序坐，如果能坐上去尽量坐上去，坐不上去就等下一辆。
分析：
直接模拟即可。
代码：
/** Author: illuz * File: a.cpp* Create Date: 2014-05-30 23:32:27* Descripton: */#include #include #include #include using namespace std;const int N = 110;int n, m, a[N];int main(){ cin >> n >> m; for (int i = 0; i < n; i++) { cin >> a[i]; } int i = 0, cnt = 0; while (i < n) { int t = m; while (t >= a[i] && i < n) { t -= a[i]; i++; } cnt++; } cout << cnt << endl; return 0;}
435B - Pasha Maximizes
题目地址
题意：
给出n个数，要求最多相邻交换k次，求能产生的最大值。
分析：
贪心。我们是为了让数尽量大，所以我们尽量让前面的数尽量大。
考虑第i位，假设前面的数都以及是尽可能大了，那它要变最大，就要找后面在可能交换过来的范围内最大的那个数，然后模拟交换过来就行了。
这样我们只要从第一位模拟过去就行了。
ps:我的这个代码只能用vc过...一直都用的g++，赛后fst我都惊呆了，发现出错的样例我在本地是跑得过的...（本地g++版本是4.8，cf上的是4.7，wa的输入是`219810011901120912 100`，哪位能告诉我这俩版本为什么有区别）【Bug fixed~】
代码：
/** Author: illuz * File: b.cpp* Create Date: 2014-05-30 23:40:23* Descripton: Bug fixed.*/#include #include #include using namespace std;const int N = 20;int k, len;char a[N];void boo() { for (int i = 0; i < len; i++) { int p = i; // p是后面能换的那些数中最大的位置 for (int j = 1; j <= k && j + i < len; j++) { if (a[i + j] > a[p]) { p = i + j; } } if (a[p] == a[i]) { // 如果一样大就没意义了 continue; } for (int j = p; j > i; j--) swap(a[j], a[j - 1]); k -= p - i; if (k <= 0) return; }}int main(){ scanf("%s%d", a, &k); len = strlen(a); boo(); printf("%s\n", a); return 0;}
435C - Cardiogram
题目地址
题意：
几乎不用看题目，只要看样例就能发现，就是求一些数，奇数上升，偶数下降，把图画出来就行了。
分析：
纯模拟。
由于It is guaranteed that the sum of all ai doesn't exceed 1000，也就是我们不需要担心会开不下数组。
直接开一个2000*1000的数组，刚开始把1000作为初始的x轴，然后模拟，并记录上下界。
刚开始没发现每行后面还要补空格，给wa了俩TAT.
代码：
/** Author: illuz * File: c.cpp* Create Date: 2014-05-31 00:22:36* Descripton: */#include #include #include using namespace std;const int N = 1010;int n, a, cx, cy, num[N * 2], up, down;char m[N * 2][N];int main(){ scanf("%d", &n); cx = N; cy = 0; up = down = N; for (int i = 0; i < n; i++) { scanf("%d", &a); if (i % 2 == 0) { while (a--) { m[cx][cy] = '/'; num[cx] = cy + 1; cx--; cy++; } cx++; up = max(cx, up); down = min(cx, down); } else { while (a--) { m[cx][cy] = '\\'; num[cx] = cy + 1; cx++; cy++; } cx--; up = max(cx, up); down = min(cx, down); } } // find the most left int left = 0; for (int i = down; i <= up; i++) left = max(left, num[i]); // Output for (int i = down; i <= up; i++) { if (num[i] != 0) { for (int j = 0; j < left; j++) if (m[i][j] == 0) putchar(' '); else putchar(m[i][j]); if (i != up) puts (""); } } return 0;}
