比赛链接: http://codeforces.com/contest/435
题目大意:
已知每辆公交车最多可以载 $m(1 <= m <= 100)$ 个人，给出 $n(1 <= n <= 100)$ 组人, 人数分别为 $a_i(1 <= i <= m)$, 每辆公交车尽量可以载更多的组, 但是不能把每组人分开载， 问把这 $n$ 组人全部载上最少需要多少辆公交车。注意: 要按顺序一组一组的上车。
解题思路:
模拟一下上车的过程即可, 每辆车尽量让更多的组上车，实在放不下再等下一辆车。
参考代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| #include <cstdio>
#include <iostream>
using namespace std;
const int MAXN = 110;
int a[MAXN];
int main(){
int n, m;
while(scanf("%d%d", &n, &m) != EOF){
for(int i = 0; i < n; i++)
scanf("%d", &a[i]);
a[n] = 111111;
int cnt = 0;
int tmp = m;
for(int i = 0; i <= n; i++){
if(a[i] > tmp){
cnt++;
tmp = (m - a[i]);
}else{
tmp -= a[i];
}
}
printf("%d\n", cnt);
}
return 0;
}
|
题目大意:
给定两个数字 $a(1 <= a <= 10^{18}), k(0 <= k <= 100), a$ 是一个没有前导零的整数, 现在对数字 $a$ 进行操作, 每次操作可以把 $a$ 中两个相邻的数字交换位置, 问经过 $k$ 次操作后，$a$ 的值最大是多少。
解题思路:
贪心, 但是要注意贪心的方法。假设我们现在考虑第 $i$ 位，比 $i$ 更高的位已经是最大的数字, 我们需要找到 $k$ 步以内的最大的数字把它移到第 $i$ 位，然后再考虑下一位。具体看代码。
参考代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| #include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 110;
char ch[MAXN];
int n, m, k;
int main(){
while(scanf("%s%d", ch, &k) != EOF){
int len = strlen(ch);
for(int i = 0; i < len; i++){
int ma = ch[i] - '0', map = i;
for(int j = i + 1; j <= i + k && j < len; j++)
if(ch[j] - '0' > ma) ma = ch[j] - '0', map = j;
for(int j = map; j > i; j--){
swap(ch[j], ch[j - 1]);
k--;
}
if(k <= 0) break;
}
printf("%s\n", ch);
}
return 0;
}
|
题目大意:
输出一个心电图，给定 $n(2 <= n <= 1000)$ 步操作，对于第 $i(1 <= i <= n)$ 步操作，当 $i$ 为奇数时输出’/‘, 当 $i$ 为偶数时输出’', 例如:
解题思路:
模拟，虽然题目说 $\sum_{n}^{i=1}a_i <= 1000$, 但是出于保险考虑还是开了一个 2000 * 2000 的数组。
参考代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| #include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int MAXN = 2001;
char ch[MAXN][MAXN];
int main(){
int n;
while(scanf("%d", &n) != EOF){
fill(ch[0], ch[MAXN], ' ');
int v;
int ma = 1000, mi = 1000;
int dx = 0, dy = 1000;
for(int i = 1; i <= n; i++){
scanf("%d", &v);
if(i & 1){
while(v--){
ch[dy][dx] = '/';
if(v) dy++;
dx++;
}
ma = max(ma, dy);
} else{
while(v--){
ch[dy][dx] = '\\';
if(v) dy--;
dx++;
}
mi = min(mi, dy);
}
}
for(int i = mi; i <= ma; i++)
ch[i][dx] = '\0';
for(int i = ma; i >= mi; i--)
printf("%s\n", ch[i]);
}
return 0;
}
|
