APCS 2021/01 不負責程式碼範例

1. 購買力

題目敘述

//#include <bits/stdc++.h>
#include <iostream>
#include <math.h>
using namespace std;
int main(){
	int n, d, a[3];
	cin >> n >> d;
	int cnt = 0, sum = 0;
	for(int i = 0; i < n; i++){
		cin >> a[0] >> a[1] >> a[2];
		sort(a, a+3);
		if(a[2] - a[0] >= d){
			cnt++;
			sum += (a[0] + a[1] + a[2])/3;
		}
	}
	cout << cnt << " " << sum << endl;
	return 0;
}

2. 流量

題目敘述

//#include <bits/stdc++.h>
#include <iostream>
using namespace std;
#define N 51
// server to city: mxn array
int Q[N][N];
// city flow: mxm array
int f[N][N] = {{0}};
int c[N];
int main(){
	int n, m, k;
	cin >> n >> m >> k;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			cin >> Q[i][j];
		}
	}

	int min, cost;
	for(int x = 0; x < k; x++){
		//	reset city flow array
		for(int i = 0; i < m; i++){
			for(int j = 0; j < m; j++){
				f[i][j] = 0;
			}
		}
		// count city flow according to specific cases
		cost = 0;
		for(int i = 0; i < n; i++){
			cin >> c[i];
			for(int j = 0; j < m; j++){
				f[c[i]][j] += Q[i][j];
			}
		}
		// count cost
		for(int i = 0; i < m; i++){
			for(int j = 0; j < m; j++){
				if(i == j)	
					cost += f[i][j];
				else if (f[i][j] <= 1000)
					cost += 3*f[i][j];
				else
					cost += 3000 + 2*(f[i][j]-1000);	
			}
		}
		if (x == 0 || cost < min)	min = cost;
	}
	cout << min << endl;
}

3. 切割費用

題目敘述

【會TLE的解法】依切割順序排序，遞迴解

#include <bits/stdc++.h>
using namespace std;
#define N 200002
typedef long long LL;
struct Cut{
	int x;
	int i;
};

bool icmp(Cut a, Cut b){
	return a.i < b.i;
}
Cut a[N];
LL cost(Cut a[], int i, int p, int q, int n){
	if (i == n-1){
		if(a[i].x > p && a[i].x < q){
			return q-p;
		} else {
			return 0;
		}
	} else if (a[i].x > p && a[i].x < q){
		return q - p + cost(a, i+1, p, a[i].x, n) + cost(a, i+1, a[i].x, q, n);
	} else {
		return cost(a, i+1, p, q, n); 
	}
}
int main(){
    int n, L;
    cin >> n >> L;
    for(int j = 0; j < n; j++){
        cin >> a[j].x >> a[j].i;
    }
    sort(a, a+n, icmp);
    cout << cost(a, 0, 0, L, n) << endl;
    return 0;
}

【可以過但很慢的解法】依切割位置排序，左右分別找出最近的較小切割點

#include <bits/stdc++.h>
using namespace std;
#define N 200002
typedef long long LL;
struct Cut{
	int x;
	int i;
};
bool xcmp(Cut a, Cut b){
	return a.x < b.x;
}
Cut a[N], b[N];
int main(){
	int n, L;
	cin >> n >> L;
	for(int j = 0; j < n; j++){
		cin >> a[j].x >> a[j].i;
	}
	for(int j = 0; j < n; j++){
		b[j].x = a[j].x;
		b[j].i = a[j].i;
	}
	sort(a, a+n, icmp);
	sort(b, b+n, xcmp);
	LL sum = 0;
	for(int j = 0; j < n; j++){
		int p = 0;
		int q = L;
		for(int k = j-1; k >= 0; k--){
			if(b[k].i < b[j].i){
				p = b[k].x;
				break;
			}
		}
		for(int k = j+1; k < n; k++){
			if(b[k].i < b[j].i){
				q = b[k].x;
				break;
			}
		}
		sum += q-p;
		//cout << "Point " << j << ", add " << q-p << endl;
	}
	cout << sum << endl;
    return 0;
}

幾種解法參考

【Sol 1 範例解法】先備知識：STL stack

#include <bits/stdc++.h>
using namespace std;
#define N 200002
typedef long long LL;
struct Cut{
	int x;
	int i;
};
bool xcmp(Cut a, Cut b){
	return a.x < b.x;
}
stack<Cut> S;
Cut a[N];
int main(){
	int n, L;
	cin >> n >> L;
	for(int j = 0; j < n; j++){
		cin >> a[j].x >> a[j].i;
	}
	sort(a, a+n, xcmp);
	LL sum = 0;
	Cut h = {0, 0};
	Cut t = {L, 0};
	S.push(h);
	for(int i = 0; i < n; i++){
		while(a[i].i < S.top().i){
			S.pop();
		}
		sum += a[i].x - S.top().x;
		S.push(a[i]);
	}
	while(!S.empty()){
		S.pop();
	}
	S.push(t);
	for(int i = n-1; i >= 0; i--){
		while(a[i].i < S.top().i){
			S.pop();
		}
		sum += S.top().x - a[i].x;
		S.push(a[i]);
	}
	cout << sum << endl;
	return 0;
}

【Sol 2 範例解法】先備知識：STL set、iterator

請參考YUI HUANG的演算法筆記