實作題

C++

出題內容:

一維 array[ ]

/*
 * zerojudge
 * f605. 1. 購買力
*/
#include<bits/stdc++.h>
using namespace std;

int main(){
	int n,d;
	cin >> n >> d;
	int sum = 0;
	int cnt = 0;
	while(n--){
		int x=0,M=0,m=0,now=0;
		cin >> x;
		now += x;
		M = x;
		m = x;
		cin >> x;
		now += x;
		M = max(M,x);
		m = min(m,x);
		cin >> x;
		now += x;
		M = max(M,x);
		m = min(m,x);
		//
		if(M-m>=d){
			cnt += 1;
			sum += now/3;
		}
	}
	cout << cnt << " " << sum << endl;
}

二維 array[ ][ ]

/*
 * zerojudge
 * f606. 2. 流量
*/
#include<bits/stdc++.h>
using namespace std;

int main() {
    int n, m, k;
    cin >> n >> m >> k;

    int server[55][55];

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> server[i][j];
        }
    }

    int minCost = INT_MAX;

    while (k--) {
        int flow[55][55] = {0};
        int city, cost = 0;

        for (int i = 0; i < n; i++) {
            cin >> city;
            for (int j = 0; j < m; j++) {
                flow[city][j] += server[i][j];
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < m; j++) {
                if (i == j) {
                    cost += flow[i][j];
                } else {
                    if (flow[i][j] >= 1000) {
                        cost += 3000 + 2 * (flow[i][j] - 1000);
                    } else {
                        cost += 3 * flow[i][j];
                    }
                }
            }
        }

        minCost = min(minCost, cost);
    }

    cout << minCost << endl;

    return 0;
}

資料結構 Set

/*
 * zerojudge
 * f607. 3. 切割費用
*/
#include<bits/stdc++.h>
using namespace std;

set<int>st;

int main(){
	long long ans=0;
	int n,l;
    cin >> n >> l;
    int cut[n+1];
    for(int i=1;i<=n;i++){
    	int a,b;
        cin >> a >> b;
        cut[b] = a;
    }
    st.insert(0);
    st.insert(l);
    for(int i=1;i<=n;i++){
        st.insert(cut[i]);
        auto pre=st.find(cut[i]);
        auto nxt=st.find(cut[i]);
        pre--;
        nxt++;
        ans+=*nxt-*pre;
    }
    cout<<ans;
}

演算法 LIS

/*
 * zerojudge
 * f608. 4. 飛黃騰達
*/
#include<bits/stdc++.h>
using namespace std;

struct T{
	int x;
	int y;
};

bool cmp(T a,T b){
	return a.x<b.x;
}

int main(){
	int n;
	cin >> n;
	T food[n];
	vector<int> dp(n, 1);
	for(int i=0;i<n;++i){
		cin >> food[i].x >> food[i].y;
	}
	sort(food,food+n,cmp);
	//
	vector<int> ans;

    for(T num : food) {
        if (ans.empty() || ans.back() < num.y) {
            ans.push_back(num.y); // 大於 代表有遞增
        } else {
            auto it = upper_bound(ans.begin(), ans.end(), num.y);
            *it = num.y; // 換小點的y 有可能可以接更多
        }
    }

    cout << ans.size() << endl;

    return 0;
}