# APCS 2021/1 題解
## ==購買力==
### <font color="0E81A6">題目</font>
[購買力](https://zerojudge.tw/ShowProblem?problemid=f605)
### <font color="0E81A6">核心</font>
條件判斷
### <font color="0E81A6">思路</font>
歷屆中算簡單的一題。

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,d,num=0,sum=0;
    int A[3];
    scanf("%d%d",&n,&d);
    for(int i=0;i<n;i++)
    {
        scanf("%d%d%d",A,A+1,A+2);
        if(abs(A[0]-A[1])>=d||abs(A[0]-A[2])>=d||abs(A[1]-A[2])>=d)
            num++,sum+=(A[0]+A[1]+A[2])/3;
    }
    printf("%d %d\n",num,sum);
}

## ==流量==
### <font color="0E81A6">題目</font>
[流量](https://zerojudge.tw/ShowProblem?problemid=f606)
### <font color="0E81A6">核心</font>
二維陣列、模擬
### <font color="0E81A6">思路</font>
沒想像中複雜，用兩個二維就能簡單模擬。
server[i][j]表編號i伺服器流向編號j城市的流量。
flow[i][[j]表編號i城市流向編號j城市的總流量。

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,m,k;
    int server[55][55];
    scanf("%d%d%d",&n,&m,&k);
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++) scanf("%d",&server[i][j]);
    }
    int minCost=INT_MAX;
    while(k--)
    {
        int flow[55][55]={0},city,cost=0;
        for(int i=0;i<n;i++)
        {
            scanf("%d",&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);
    }
    printf("%d\n",minCost);
}

## ==切割費用==
### <font color="0E81A6">題目</font>
[切割費用](https://zerojudge.tw/ShowProblem?problemid=f607)
### <font color="0E81A6">核心</font>
排序、二分搜
### <font color="0E81A6">思路</font>
切過後視為一端點，插入set，每次切割找尋最近左右端點。

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define pii pair<int,int>
#define N 200005
int n,L;
pii cut[N];
set<int> point;
int main()
{
    scanf("%d%d",&n,&L);
    for(int i=0;i<n;i++)
    {
        int locate,which;
        scanf("%d%d",&locate,&which);
        cut[i].first=which,cut[i].second=locate;
    }
    point.insert(0),point.insert(L);
    sort(cut,cut+n);
    LL cost=0;
    for(int i=0;i<n;i++)
    {
        int place=cut[i].second;
        auto it=point.lower_bound(place);
        int leftPoint=*(prev(it)),rightPoint=*it;
        cost+=rightPoint-leftPoint;
        point.insert(place);
    }
    printf("%lld\n",cost);
}

## ==飛黃騰達==
### <font color="0E81A6">題目</font>
[飛黃騰達](https://zerojudge.tw/ShowProblem?problemid=f608)
### <font color="0E81A6">核心</font>
排序、二分搜
### <font color="0E81A6">思路</font>
以x方向或y方向作排序，接著依序去找另一方向的最長遞增序列。

注意!tmp內所放的值非路徑解，tmp只能求最多經過點數量。
當tmp.back()小於目前所看的點另一方向值時，所進行的是tmp內值的修改(此時當前最佳路徑已不在tmp內，但最佳長度保持)，若修改有助於後續推入更多點(tmp.back()也被修改為較小值)，最佳路徑改變，長度增加，若修改無助於後續推入更多點，也不影響最佳長度。(當作是一種未知的考量)

#include<bits/stdc++.h>
#define F first
#define S second
using namespace std;
int n;
vector<pair<int,int>>v;
int main()
{
    cin>>n;
    v.assign(n,{});
    for(int i=0;i<n;i++)cin>>v[i].F>>v[i].S;
    sort(v.begin(),v.end());
    vector<int>tmp;
    for(auto i:v)
    {
        if(tmp.empty()||tmp.back()<=i.S)tmp.push_back(i.S);
        else tmp[upper_bound(tmp.begin(),tmp.end(),i.S)-tmp.begin()]=i.S;
    }
    cout<<tmp.size();
}