AcWing 1241. 一次循环搞定，简单思路易理解，看不懂你打我

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 1241. 一次循环搞定，简单思路易理解，看不懂你打我原题链接简单

作者：

sdsxdxl , 2021-03-06 22:07:16 , 所有人可见 , 阅读 3499

12

3

题解：

按照每个店铺id为第一关键字，时间t为第二关键字升序排序。
把每个店铺看做一个集合label，集合中元素为该店铺的订单时间。(以下叙述均称每一个店铺为集合)
对于每一个集合，按照订单时间先后顺序扫描，扫描过程中记录该店铺的实时状态(是否在缓存中)，并记录当前的优先级。
遇到一个新集合时，此时应该判断上一个集合是否满足条件，判断末状态即可，更新答案。

细节：在遇到新集合时，上一个集合的最后一个订单时间可能不是T，那么随着时间流逝，优先级应该随着T减少，此刻应该注意判断。

时间复杂度：$O(M * logM + M)$

C++ 代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int cnt[N];
struct message
{
    int t, id;
    bool operator < (const message& m)
    {
        return id < m.id || id == m.id && t < m.t;
    }
}m[N];
int main()
{
    int n, M, T;
    scanf("%d%d%d", &n, &M, &T);
    for(int i = 0; i < M; i++)  scanf("%d%d", &m[i].t, &m[i].id);
    sort(m, m + M);
    int cur = 2, ans = 0;
    bool flag = false;

    for(int i = 1; i <= M; i++)
    {
        if(m[i].id != m[i-1].id)
        {
            if(flag && cur - (T - m[i-1].t) > 3)    ans++;      //注意判断末订单时间
            flag = false;   //恢复初始值，为当前集合服务
            cur = 2;
        }
        else
        {
            int diff = m[i].t - m[i-1].t - 1;
            if(diff == -1)   diff = 0;
            cur = max(0, cur - diff);
            if(cur <= 3)    flag = false;
            cur += 2;
            if(cur > 5)     flag = true;
        }
    }
    printf("%d\n", ans);
    return 0;
}

15 评论

AnotherLongMarch 2022-04-05 16:46

出来挨打，谢谢

nothing_sybs 2023-09-26 07:56

加了注释
可以参考下

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int cnt[N];
struct message
{
    int t, id;
    bool operator < (const message& m)//依照id和时间小到大排序
    {
        return id < m.id || id == m.id && t < m.t;
    }
}m[N];
int main()
{
    int n, M, T;
    scanf("%d%d%d", &n, &M, &T);
    for(int i = 0; i < M; i++)  scanf("%d%d", &m[i].t, &m[i].id);
    sort(m, m + M);
    //cur 代表第i-1个订单外卖店的优先级,第0个订单对应外卖店优先级为2
    int cur = 2, ans = 0;
    bool flag = false;

    for(int i = 1; i <= M; i++)//枚举后m个订单，第m个为空订单
    {
        if(m[i].id != m[i-1].id)//如果为新外卖店订单,结算前面的
        {   
            //加入到优先缓存且最后没有被清除出
            if(flag && cur - (T - m[i-1].t) > 3)    ans++;      //注意判断末订单时间
            flag = false;   //恢复初始值，为当前集合服务
            cur = 2;
        }
        else
        {
            int diff = m[i].t - m[i-1].t - 1;//diff表示没有订单减少的优先级
            if(diff == -1)   diff = 0;//相同时间有多组订单，不减少
            cur = max(0, cur - diff);//最多减少到0
            if(cur <= 3)    flag = false;//等价于+2后小于等于5，标记一下，防止误判
            cur += 2;
            if(cur > 5)     flag = true;//加入到优先缓存中
        }
    }
    printf("%d\n", ans);
    return 0;
}

李赫666 2022-05-31 07:52

思路太好了

杨南邦 8个月前

草稿纸比划了下，发现代码思路很清晰

试错 2021-04-16 20:05

出来挨打谢谢

清风揽月 1个月前

ORZ一直都是考虑给时间排序一个点一个点处理，给ID排序一次处理一家店确实妙

相顾无言 9个月前

``package com.zeng.acwing;

import java.util.Arrays;
import java.util.Scanner;

class Pair implements Comparable[HTML_REMOVED] {
int ts, id;
public Pair(int ts, int id) {
this.id = id;
this.ts = ts;
}

@Override
public int compareTo(Pair o) {
    if (this.id != o.id) return this.id - o.id; // 升序排序

    return this.ts - o.ts; // 小的排前面
}

}
public class Main {
public static int cnt = 0, n, m, T;
public static final int N = 100010;
public static Pair[] g = new Pair[N];
public static int[] p = new int[N];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
T = sc.nextInt();
for (int i = 0; i < m; i++) {
g[i] = new Pair(sc.nextInt(), sc.nextInt());
}
Arrays.sort(g, 0, m);
int prevId = 0, prevTs = 0, sum = 0;
boolean flag = false;

    for (int i = 0; i < m; i++) {
        if (g[i].id == prevId) { // 换id了肯定不相同
            int diff = (g[i].ts - prevTs);
            if (diff == 0) diff = 1; // 重复订单
            prevId = g[i].id;
            prevTs = g[i].ts;
            sum = Math.max(0, sum - (diff - 1));
            if (flag && sum < 3) flag = false;
            sum = sum + 2;
            if (sum > 5) flag = true;

        } else { // 不相同 第一个 最后一个 怎么判断 不同 看时间查了多少
            if (flag) { // 只考虑这个就行了，
                int diff = T - g[i-1].ts;
                if (sum - diff > 3)
                    cnt ++;
            }
            sum = 2;
            prevTs = g[i].ts;
            prevId = g[i].id;
            flag = false;

        }
    }
    if (flag) { // 最后一位
        int diff = T - g[m-1].ts;
        if (sum - diff > 3) cnt ++;
    }
    System.out.println(cnt);
}

}``
按你这个思路写的，不东为什么有漏几个