1 条题解

  • 0
    @ 2025-9-22 21:42:37

    这个问题需要统计每个用户在登录时,有多少其他用户在同一小时内(间隔不超过3600秒)登录。我们需要处理时间数据,并高效地计算每个用户的有缘人数量。

    关键点

    • 时间转换:将HH:mm:ss格式的时间转换为秒数

    • 有缘条件:两个用户登录时间差的绝对值不超过3600秒

    1. 将所有用户按登录时间排序

    2. 使用双指针维护一个滑动窗口,窗口内的时间差不超过3600秒

    3. 对于每个用户,统计窗口内的其他用户数量

    #include <bits/stdc++.h>
    using namespace std;
    #define int long long
    #define pii pair<int, int>
    #define fs first
    #define sc second
    #define pb emplace_back
    #define ep emplace
    #define all(x) x.begin(),x.end()
     
    constexpr int N = 1e6 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
    constexpr double PI = acos(-1.0), eps = 1e-9;
     
    void solve() {
        int n;
        cin >> n;
        vector<string> s(n + 1);
        vector<pii> t(n + 1);
        for (int i=1;i<=n;i++) {
            cin >> s[i];
            int hh, mm, ss;
            char tmp;
            cin >> hh >> tmp >> mm >> tmp >> ss;
            t[i] = {hh * 3600 + mm * 60 + ss, i};
        }
        sort(all(t));
        vector<int> cnt(n + 1);
        int l = 1, r = 1;
        for (int i=1;i<=n;i++) {
            while (t[i].fs - t[l].fs > 3600) l ++;
            while (r + 1 <= n && t[r + 1].fs - t[i].fs <= 3600) r ++;
            cnt[t[i].sc] = r - l;
        }
        for (int i=1;i<=n;i++) {
            cout << s[i] << ' ' << cnt[i] << '\n';
        }
    }
     
    signed main() {
        ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
        // init();
        int t = 1;
        // cin >> t;
        while (t--) solve();
    }
    
    
    • 1

    信息

    ID
    2730
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    (无)
    递交数
    4
    已通过
    1
    上传者