Acwing枚举、模拟与排序（二）

WuShF

发布于 2024-03-08 08:34:02

810

发布于 2024-03-08 08:34:02

文章被收录于专栏：笔记分享笔记分享

回文日期

原文链接：https://www.acwing.com/problem/content/468/

由于只有八位数，而且回文串左右对称，因此可以只枚举左半边。然后判断：

整个八位数日期是否合法
是否在范围内

一共枚举1e4个数。判断过程是常数级别的，所以总计算量是

O(10^4)

代码中的check属于基操。

#include"bits/stdc++.h"

using namespace std;
int date1, date2;
int months[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

bool check(int date) {
    int year = date / 10000;
    int month = date % 10000 / 100;
    int day = date % 100;

    if (!month || month >= 13 || !day) return false;

    if (month != 2 && day > months[month]) return false;
    if (month == 2) {
        bool leap = year % 4 == 0 && year % 100 || year % 400 == 0;
        if (day > 28 + leap) return false;
    }

    return true;
}


int main() {
    int res = 0;
    cin >> date1 >> date2;
    for (int i = date1 / 1e4; i < date2 / 1e4; i++) {
        int date = i, tmp = i;
        for (int j = 0; j < 4; j++)date = date * 10 + tmp % 10, tmp /= 10;
        if (date >= date1 && date <= date2 && check(date))res++;
    }
    cout << res << endl;
    return 0;
}

参考

https://www.acwing.com/solution/content/3897/

日期问题

原题链接：https://www.acwing.com/problem/content/1231/

真就是在枚举。

#include"bits/stdc++.h"

using namespace std;

int days[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

int check(int year, int month, int day) {
    if (month > 12 || month < 1)return false;
    if (day == 0)return false;
    if (month != 2) {
        if (day > days[month])return false;
    } else {
        int leap = year % 4 == 0 && year % 100 || year % 400 == 0;
        if (day > 28 + leap)return false;
    }
    return true;
}

int a, b, c;

int main() {
    scanf("%d/%d/%d", &a, &b, &c);
    for (int date = 19600101; date <= 20591231; date++) {
        int year = date / 10000, month = date / 100 % 100, day = date % 100;
        if (check(year, month, day)) {
            if (year % 100 == a && month == b && day == c ||
                month == a && day == b && year % 100 == c ||
                day == a && month == b && year % 100 == c) {
                printf("%d-%02d-%02d\n", year, month, day);
            }
        }
    }
    return 0;
}

航班时间

原题链接：https://www.acwing.com/problem/content/1233/

不知道时差是多少，要求真实的飞行时间。去的时候，从东向西，减时差：

飞行时间=起降时间之差-时差

回的时候，从西向东，加时差：

飞行时间=起降时间之差+时差

两式作和，然后除以二，就可以求出飞行时间。

将所有时间转换成距离当天00:00:00的秒数。
按行读入，对于行末可能有也可能没有的()，格式化统一处理。

cin和scanf都不会干掉第一行的回车。在这些函数执行完成之后，执行getline之前，多执行一次getline：去掉回车。

#include"bits/stdc++.h"

using namespace std;


int t;

int getSecond(int h, int m, int s) {
    return h * 3600 + m * 60 + s;
}

int getTime() {
    string line;
    getline(cin, line);
    if (line.back() != ')')
        line += " (+0)";
    for (int i = 0; i < 2; i++) {
        int h1, m1, s1, h2, m2, s2, d;
        sscanf(line.c_str(), "%d:%d:%d %d:%d:%d (+%d)", &h1, &m1, &s1, &h2, &m2, &s2, &d);
        return getSecond(h2, m2, s2) - getSecond(h1, m1, s1) + d * 24 * 3600;
    }
}

int main() {
    cin >> t;
    //忽略第一行的回车
    string line;
    getline(cin, line);
    while (t--) {
        int time = (getTime() + getTime()) >> 1;
        int hour = time / 3600, minute = time % 3600 / 60, second = time % 60;
        printf("%02d:%02d:%02d\n", hour, minute, second);
    }
    return 0;
}

外卖店优先级

原题链接：https://www.acwing.com/problem/content/1243/

数据量为1e5，如果按时间顺序枚举每一份订单，很有可能超时。在整个过程中，有一部分时间是没有订单的，这一部分就可以暂时跳过。等到有订单的时候再来处理。这样，只有在有订单的时间点才去处理数据，而非遍历从头到尾的每个时刻。减少数据量。这就需要：在枚举之前，先对订单数组按时间排序。然后，按时间顺序遍历订单。遍历每个订单时，查看上一次该店铺收到订单的时间。存储该时间需要创建一个数组，店铺号作为下标，值为上一次的订单时间。

先减去时间差，统一处理之前的无订单事件。
再提高优先级，处理订单事件。

如果当前店铺的最后一个订单不在最后一个时刻。那么遍历订单的时候，不会再遍历到该店铺，不会进入上面两步，处理该店铺的无订单事件，但是这期间，该店铺的优先级在持续降低。解决方案就是，在最后一个时刻，遍历所有店铺上一次订单的时间。统一处理无订单事件。

#include"bits/stdc++.h"

using namespace std;

#define x first
#define y second
typedef pair<int, int> PII;
int n, m, T;
PII order[100010];
int score[100010], last[100010], st[100010];

int main() {
    cin >> n >> m >> T;
    for (int i = 0; i < m; i++)scanf("%d%d", &order[i].x, &order[i].y);
    sort(order, order + m);
    for (int i = 0; i < m;) {
        int j = i;
        while (j < m && order[j] == order[i])j++;
        int t = order[i].x, id = order[i].y, cnt = j - i;
        i = j;
        score[id] -= t - last[id] - 1;
        if (score[id] < 0)score[id] = 0;
        if (score[id] <= 3)st[id] = false;
        score[id] += cnt * 2;
        if (score[id] > 5)st[id] = true;
        last[id] = t;
    }
    for (int i = 1; i <= n; i++) {
        if (last[i] < T) {
            score[i] -= T - last[i];
            if (score[i] <= 3)st[i] = false;
        }
    }
    int res = 0;
    for (int i = 0; i <= n; i++)res += st[i];
    cout << res << endl;
    return 0;
}

上面的代码中，比较费解的是：

for (int i = 0; i < m;) {
    int j = i;
    while (j < m && order[j] == order[i])j++;
    int t = order[i].x, id = order[i].y, cnt = j - i;
    i = j;
    score[id] -= t - last[id] - 1;
    if (score[id] < 0)score[id] = 0;
    if (score[id] <= 3)st[id] = false;
    score[id] += cnt * 2;
    if (score[id] > 5)st[id] = true;
    last[id] = t;
}

order是一个pair二元组，.first和.second的值分别是时间和店铺。 while()的结束条件是：

j已经移动到了数组边界之外。
或order订单二元组不完全相等。

这是因为同一时刻，可能有多个指向同一店铺的订单，同无订单事件一样。也可以集中处理。这个循环的作用，就是统计相同的订单的数量。相同订单的条件是，时间和店铺相同。每个订单都会提供2点优先级，因此后面的代码中有score[id] += cnt * 2; 所以，上面这段代码的作用是：

枚举每一个订单。（枚举之前已经排序）
对于当前订单，相同的订单的数量，并将指针移动到下一个不同的订单。
处理当前订单指向的店铺，之前的“无订单”事件。
处理当前订单指向的店铺，当前的“有订单”事件。
更新last数组，存储的是，当前订单指向的店铺，的上一次订单时刻。

逆序对的数量

原题链接：https://www.acwing.com/problem/content/790/

归并排序：

[L,R]=>[L,mid],[mid+1,R]
递归排序[L,mid]和[mid+1,R]
归并，将左右两个有序序列合并成一个有序序列

以mid为分界点，逆序对的两个数可能同时出现在左半边，也可能同时出现在右半边，也可能一个在左一个在右。各区间内的逆序对数量：

左半边内部的逆序对数量：merge_sort(L,mid)
右半边内部的逆序对数量：merge_sort(mid+1,R)

一个在左一个在右的情况：在左半部分和右半部分时，假设已经排好序了，并且返回了所在区间的逆序对数量。对左半部分和右半部分继续归并排序，左区间指针大于右区间指针时，由于左右区间已经分别排好序了，那么左区间指针右侧的值都大于右区间指针当前指向的值，左区间的较大值都可以与右区间当前值构成逆序对。符合要求的取值的数量就等于mid-i+1。也就是用两个指针，每次发现右侧有较小值时，答案加上mid-i+1。当一侧指针指到结束位置的时候，扫尾。扫尾的时候不需要修改答案。

#include"bits/stdc++.h"

using namespace std;

typedef long long LL;
int q[100010], tmp[100010];
int n;

LL merge_sort(int l, int r) {
    if (l >= r)return 0;
    int mid = l + r >> 1;
    LL res = merge_sort(l, mid) + merge_sort(mid + 1, r);
    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j])tmp[k++] = q[i++];
        else {
            tmp[k++] = q[j++];
            res += mid - i + 1;
        }
    while (i <= mid)tmp[k++] = q[i++];
    while (j <= r)tmp[k++] = q[j++];
    for (int i = l, j = 0; i <= r; i++, j++)q[i] = tmp[j];
    return res;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++)cin >> q[i];
    cout << merge_sort(0, n - 1) << endl;
    return 0;
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2024-03-07，如有侵权请联系 cloudcommunity@tencent.com 删除

指针