寻找偏序关系

HZOJ-505 最大整数

A+B>B+A

bool compare(string a, string b)
{
    return a + b > b + a;
}
int main()
{
    int n;
    cin >> n;
    vector<string> nums(n);
    for (int i = 0; i < n; i++)
    {
        cin >> nums[i];
    }
    sort(nums.begin(), nums.end(), compare);
    for (int i = 0; i < n; i++)
    {
        cout << nums[i];
    }
    return 0;
}

HZOJ-504 删数

局部： 每次删除一个离最高位最近的逆序位的第一个数字 1234321，其中43是离最高位最近的逆序位，删除4即可

整体： 按照如上策略执行 n 次以后，得到的就是最小的整数

int main()
{
    string s;
    int k;
    cin >> s >> k;
    for (int i = 0; i < k; i++)
    {
        int j = 0;
        while (s[j] <= s[j + 1] && (j + 1) < s.size())
            j++;
        for (int k = j; k < s.size() - 1; k++)
            s[k] = s[k + 1];
    }
    int flag = 0;
    for (int i = 0; i < s.size() - k; i++)
    {
        if (s[i] != '0')
            flag = 1;
        if (flag == 1)
            cout << s[i];
    }
    return 0;
}

HZOJ-503 独木舟

假设：独木舟承重 w，人员全集是 A，子集分别为 X1与 X2，且 X1 + X2 = A，F 函数返回最少的独木舟数量
证明：F(A) ≤ F(X1) + F(X2)

int main()
{
    int w, n;
    cin >> w >> n;
    int nums[n];
    for (int i = 0; i < n; i++)
    {
        cin >> nums[i];
    }
    sort(nums, nums + n);
    int i = 0, j = n - 1;
    int ans = 0;
    while (i<j)
    {
        if (nums[i] + nums[j] <= w)
        {
            ans++;
            i++;
            j--;
        }
        else
        {
            j--;
            ans++;
        }
    }
    if (i == j)
        ans++;
    cout << ans;
    return 0;
}

每次安排，如果最重的人和最轻的人能坐一起，就坐一 条独木舟，否则最重的人自己坐一条船。

证明： F(x1~xn) = MIN[ F(xn) + F(x1~xn-1) , F(x1xn) + F(x2~xn-1) ]

HZOJ-258 最大子阵和

转换为一维最大子序和问题

int main() {
    int n;
    cin >> n;
    vector<vector<int>>arr(n+1,vector<int>(n+1, 0));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> arr[i][j];
            arr[i][j] += arr[i - 1][j];
        }
    }
    int ans = arr[0][0];
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j <= n; j++) {
            int s = 0;
            for (int k = 1; k <= n; k++) {
                int a = arr[j][k] - arr[i][k];
                if (s >= 0) s += a;
                else s = a;
                ans=max(s,ans);
            }
        }
    }
    cout << ans << endl;
    return 0;
}

HZOJ-511 最少操作次数

int main()
{
    long long a, b, k, ans = 0;
    cin >> a >> b >> k;
    if (k <= 1 || a == 0)
        ans = b - a;
    else
    {
        while (b > a)
        {
            if (a * k <= b)
            {
                ans += 1 + b % k;
                b /= k;
            }
            else
            {
                ans += b - a;
                break;
            }
        }
    }
    cout << ans;
    return 0;
}

HZOJ-255 安装雷达

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

struct Range {
    double l, r;
};

bool cmp(const Range &a, const Range &b) {
    return a.r < b.r;
}

int main() {
    int n;
    double d, x, y;
    cin >> n >> d;
    Range ranges[n];

    for (int i = 0; i < n; i++) {
        cin >> x >> y;
        if (y > d) {
            cout << -1 << endl;
            return 0;
        }
        double a = sqrt(d * d - y * y);
        ranges[i].l = x - a;
        ranges[i].r = x + a;
    }

    sort(ranges, ranges + n, cmp);

    double pos = ranges[0].r;
    int ans = 1;

    for (int i = 1; i < n; i++) {
        if (ranges[i].l > pos) {
            ans++;
            pos = ranges[i].r;
        }
    }

    cout << ans << endl;
    return 0;
}

HZOJ-254 挤奶

int m_time[500005], ans[500005];
int cnt =0;

struct Cow {
    int l, r,id;
}arr[100005];
bool cmp(Cow a,Cow b){
    if (a.l != b.l) return a.l < b.l;
    return a.id < b.id;
}
int main() {
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>arr[i].l>>arr[i].r;
        arr[i].id=i;
    }
    sort(arr,arr+n,cmp);
    memset(m_time, 0, sizeof(m_time));
    memset(ans, 0, sizeof(ans));
    for (int i = 0; i < n; i++) {
        int pos = -1;
        for (int j = 0; j < cnt; j++) {
            if (m_time[j] < arr[i].l) {
                pos = j;
                break;
            }
        }
        if (pos == -1){
            pos=cnt;
            cnt++;
        }
        m_time[pos] = arr[i].r;
        ans[arr[i].id] = pos + 1;
    }
    cout<<cnt<<endl;
    for (int i = 0; i < n; i++) {
        cout<<ans[i]<<endl;
    }
    return 0;
}

HZOJ-253 奶牛晒太阳

#define MAX_N 2500

struct Data {
    int a, b;
};

Data cow[MAX_N + 5], item[MAX_N + 5];

bool cmp(const Data &a, const Data &b) {
    if (a.b != b.b) return a.b < b.b;
    return a.a < b.a;
}

int main() {
    int C, L;
    cin >> C >> L;
    for (int i = 0; i < C; i++) {
        cin >> cow[i].a >> cow[i].b;
    }
    for (int i = 0; i < L; i++) {
        cin >> item[i].b >> item[i].a;
    }
    sort(item, item + L, cmp);
    sort(cow, cow + C, cmp);
    int ans = 0;
    for (int i = 0; i < C; i++) {
        int flag = 0;
        for (int j = 0; j < L; j++) {
            if (item[j].a == 0) continue;
            if (item[j].b <= cow[i].b && item[j].b >= cow[i].a) {
                flag = 1;
                item[j].a -= 1;
                break;
            }
        }
        ans += flag;
    }
    cout << ans << endl;
    return 0;
}

HZOJ-259 公司的颜色

struct Data {
    int x, y;
};
Data task[100005], ma[100005];
int cnt[105] = {0};//cnt[i]代表能处理难度系数为i的机器有多少台

bool cmp(const Data &a, const Data &b) {
    if (a.x==b.x) return a.y > b.y;
    return a.x > b.x;
}
int main() {
    int n,m;
    cin>>n>>m;
    long long task_cnt = 0,ans=0;
    for (int i = 0; i < n; i++) {
        cin>>ma[i].x>>ma[i].y;
    }
    for (int i = 0; i < m; i++) {
        cin>>task[i].x>>task[i].y;
    }
    sort(ma, ma + n, cmp);
    sort(task, task + m, cmp);
    for(int i=0,j=0;i<m;i++){
        while(j < n && ma[j].x >= task[i].x) {
            cnt[ma[j].y] += 1;
            j += 1;
        }
        for (int y = task[i].y; y <= 100; y++) {
            if (cnt[y] == 0) continue;
            cnt[y] -= 1;
            ans += 500 * task[i].x + 2 * task[i].y;
            task_cnt += 1;
            break;
        }
    }
    cout << task_cnt << " " << ans << endl;
    return 0;
}

HZOJ-257 树的颜色

结论1：x 是最大值节点，一旦x的父节点y被染色， 下一个染色的一定是 x 节点
结论2：对于y与其他节点z，若想要先染色y，则必须满足z<(y+x)/2
因此，我们可以将y与x等价为一个节点，相当于产生了一个额外代价x

#define MAX_N 1000
int C[MAX_N + 5] = {0};
int fa[MAX_N + 5] = {0};//父节点
int vis[MAX_N + 5] = {0};//检查是否被合并
int cnt[MAX_N + 5] = {0};//记录节点中包含原始阶段数量
double w[MAX_N + 5] = {0};//用于比较的权值
int n,r;
long long ans=0;

int find_x() {
    int x = -1;
    for (int i = 1; i <= n; i++) {
        if (i == r || vis[i] == 1) continue;
        if (x == -1 || w[x] < w[i]) x = i;
    }
    return x;
}
int find_father(int x) {//寻找没有被合并的父节点
    if (vis[fa[x]]) return find_father(fa[x]);
    return fa[x];
}

int main() {
    cin>>n>>r;
    for (int i = 1; i <= n; i++) {
        cin >> C[i];
        ans += C[i];
        fa[i] = i;
        w[i] = C[i];
        cnt[i] = 1;
    }
    for (int i = 1, a, b; i < n; i++) {
        cin >> a >> b;
        fa[b] = a;
    }
    for (int i = 1; i < n; i++) {
        int x = find_x();
        int father_x = find_father(x);
        ans += cnt[father_x] * C[x];
        C[father_x] += C[x];
        cnt[father_x] += cnt[x];
        w[father_x] = 1.0 * C[father_x] / cnt[father_x];
        vis[x] = 1;
    }
    return 0;
}