2.(郊游活动)有n名同学参加学校组织的郊游活动,已知学校给这 n 名同学的郊游总经费为 A 元,与此同时第 i 位同学自己携带了 Mi 元。为了方便郊游,活动地点提供 B(≥n)辆自行车供人租用,租用第 j 辆自行车的价格为 Cj元,每位同学可以使用自己携带的钱或者学校的郊游经费,为了方便账务管理,每位同学只能为自己租用自行车,且不会借钱给他人,他们想知道最多有多少位同学能够租用到自行车。 ( 第四、五空 2.5 分,其余 3 分)
本题采用二分法。对于区间[l, r], 我们取中间点 mid 并判断租用到自行车的人数能否达到 mid。判断的过程是利用贪心算法实现的。 #include using namespace std; #define MAXN 1000000
int n, B, A, M[MAXN], C[MAXN], l, r, ans, mid; bool check(int nn) {
int count = 0, i, j; i = (1) ; j = 1;
while (i <= n) {
if ( (2) )
count += C[j] - M[i]; i++; j++; }
return (3) ; }
void sort(int a[], int l, int r) {
int i = l, j = r, x = a[(l + r) / 2], y; while (i <= j) {
while (a[i] < x) i++; while (a[j] > x) j--; if (i <= j) {
y = a[i]; a[i] = a[j]; a[j] = y; i++; j--; } }
if (i < r) sort(a, i, r); if (l < j) sort(a, l, j);
文档
实用
}
int main() {
int i;
cin >> n >> B >> A;
for (i = 1; i <= n; i++) cin >> M[i];
for (i = 1; i <= B; i++) cin >> C[i]; sort(M, 1, n); sort(C, 1, B); l = 0; r = n;
while (l <= r) {
mid = (l + r) / 2; if ( (4) ) {
ans = mid; l = mid + 1; }
else r = (5) ; }
cout << ans << endl; return 0; }
文档
实用
第二十二届全国青少年信息学奥林匹克联赛初赛
普及组参考答案
一.选择题
DCDCD CBBCA DBDAD BAACC 二.问题求解
1. 72
2. 1(2分) 11(3分) 三.阅读程序写结果 1. 6,1,3 2. 13
3. 6,5,4,3,2,1,
4. =
四.完善程序 1.
(1)cin.get()
(2)num=c-‘0’ 或 num=c-48
(3)c>=’0’&&c<=’9’ 或 c>=48&&c<=57 (4) num=num*10+c-'0' 或 num=num*10+c-48 (5) num=-num 或 return-num 2.
(1) n-nn+1
(2) M[i]
文档