NOIP2016信息学奥赛普及组初赛C++试题及答案 较完美版(2)

int a, b;

a = readint(); b = readint();

cout<

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]