b964. 第 1 題 成績指標

#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;

const int MAX_N = 26;

int a[MAX_N];

int main () {
    int n;
    while (scanf("%d",&n) != EOF) {
        for (int i=1;n>=i;i++) {
            scanf("%d",&a[i]);
        }
        sort(a+1,a+n+1);
        int best=-1,worst=-1;
        for (int i=1;n>=i;i++) {
            if (i!=1) printf(" ");
            printf("%d",a[i]);
            if (a[i] >= 60 && worst==-1) worst=a[i];
            if (a[i] < 60) best=a[i];
        }
        puts("");
        if (best==-1) puts("best case");
        else printf("%d\n",best);
        if (worst==-1) puts("worst case");
        else printf("%d\n",worst);
    }
}

第 3 題 線段覆蓋長度

TLE

#include<bits/stdc++.h>
using namespace std;
struct Line{
    int s;
    int e;
};

bool cmp(Line a,Line b){
    if(a.s<b.s){
        return true;
    }else if(a.s>b.s){
        return false;
    }else{
        return a.e<b.e;
    }
}

int main(){
    int n,ans,head,tail;
    Line lines[10000];

    while(cin>>n){
        ans=0;

        for(int i=0;i<n;i++){
            cin>>lines[i].s>>lines[i].e;
        }

        sort(lines,lines+n,cmp);

        head = lines[0].s;
        tail = lines[0].e;

        for(int i =1;i<n;i++){
            if(lines[i].s<=tail){//重疊
                if(lines[i].e>tail)
                tail = lines[i].e;
            }else{//分段
                ans+=tail-head;
                cout<<"add"<<tail-head<<endl;
                head = lines[i].s;
                tail = lines[i].e;
            }
        }
        ans+=tail-head;
        cout<<"add"<<tail-head<<endl;
        cout<<ans;
    }
}

AC(io的部分換成c++版本就會錯)

#include <cstdio>
#include <algorithm>
using namespace std;

struct Line{
    int s;
    int e;
};

bool cmp(Line a, Line b) {
    if (a.s == b.s) return (b.e> a.e);
    else return(a.s < b.s);
}
Line lines[10000];
int main() {
    int n, cnt,head,tail;
    while (scanf("%d", &n) != EOF) {
        cnt = 0;
        for (int i = 0; i<n; i++) {
            scanf("%d %d", &(lines[i].s), &(lines[i].e));
        }
        sort(lines, lines + n, cmp);//將區間的開始數值由小到大排序，
        for (int i = 0; i < n;i++) {
            head = lines[i].s;
            tail = lines[i].e;
            while ((i + 1 < n) && lines[i + 1].s < tail) {//s與e是否包含下一個區間的開始數值
                if (lines[i + 1].e <= tail) i++;//包含下一個區間的全部，忽略此區間
                else {
                    tail = lines[i + 1].e;//未包含下一個區間的全部，但有重疊，將e改成下一個區間的結束值
                    i++;
                }
            }
            cnt = cnt + tail - head;//此區間的範圍數值個數
        }
        printf("%d\n", cnt);
    }
}

b967: 第 4 題 血緣關係

https://zerojudge.tw/ShowProblem?problemid=b967

解答：http://rs-vb.blogspot.tw/2016/09/apcs-10534-c.html

#include <iostream>
#include <cmath>
#include <cstring>
#include <vector>
using namespace std;
const int MaxN = 100000; // n <= 100000
int pa[MaxN]; //父
vector <int> ch[MaxN]; //兒子們
int longlen(int x, int &h1, int &h2)
{
 h1 = h2 = 0;  //子樹中最長高h1 及次長高h2
 int len=0;
 if(ch[x].size()==0) return 0;  //葉節點的高為 0
 for(int i=0; i<ch[x].size(); ++i)
 {
  int sh1, sh2;
  int y = ch[x][i];
  int slen = longlen(y, sh1, sh2);  //遞迴找出各子樹的最長距 slen(i) -> len
  len = max(len,slen);
  if( sh1>=h2 ) // 子樹中的最長子樹若比 本子樹的次長子樹大，重排 h1,h2
  {
   h2=sh1+1;
     if(h2>h1) // swap(h1,h2)
   {
    sh1 = h1;
    h1 = h2;
    h2 = sh1;
     }
  }
 }
 return max(len,h1+h2);
}

int main(void)
{
 int j,h , n , a,b;
 while( cin >> n )
 {
  memset(pa,-1,sizeof(pa));
  for(j=0; j<n; ++j) ch[j].clear();
  // 讀 n-1 筆 關係
  for(j=1;j<n;++j) // n-1 筆
  {
   cin >> a >> b;
   ch[a].push_back(b);
     pa[b]=a;  // 上次少這行 2017/2/4更新
  }
  int rt;
  for(rt=0; rt<n; ++rt) if(pa[rt] == -1 ) break;  //找根
  int h1,h2;
  cout << longlen(rt,h1,h2) << endl;
 }
 return 0;
}