寒假刷题记录，第二天

PTA甲级

1006 Sign In and Sign Out

经典的排序算法

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int n;
struct node
{
    string id;
    int ti , to;
};
vector<node>v;
bool cmpin(node a , node b)
{
    return a.ti < b.ti;
}

bool cmpde(node a , node b)
{
    return a.to > b.to;
}

int main()
{
    cin >> n;
    while(n --)
    {
        string id;
        char ch;
        int h1 , h2 , m1 , m2 , s1 , s2;
        cin >> id >> h1 >> ch >> m1 >> ch >> s1 >> h2 >> ch >> m2 >> ch >> s2;
        v.push_back({id , h1 * 3600 + m1 * 60 + s1 , h2 * 3600 + m2 * 60 + s2});
    }
    sort(v.begin() , v.end() , cmpin);
    cout << v[0].id << " ";
    sort(v.begin() , v.end() , cmpde);
    cout << v[0].id;
    return 0;
}

1007 Maximum Subsequence Sum

有点dp的样子

#include<iostream>

using namespace std;

const int N = 1e6 + 10;
typedef long long ll;
ll a[N];
ll sum = 0 , res = -1;
ll l = 0 , r = 0;
ll n;

int main()
{
    cin >> n;
    ll t = 0;
    r = n - 1;
    for(int i = 0;i < n;i ++)
    {
        cin >> a[i];
        sum += a[i];
        if(sum < 0)
        { //  重新计算
            sum = 0;
            t = i + 1;
        }
        else if(sum > res)
        {
            res = sum;
            r = i;
            l = t;
        }
    }

    if(res < 0) res = 0;
    cout << res << " " << a[l] << " " << a[r] << endl;
    return 0;
}