当前位置:网站首页>【练习-10】 Unread Messages(未读消息)
【练习-10】 Unread Messages(未读消息)
2022-07-06 09:26:00 【火焰车】
题目描述
There is a group of people in an internet email message group. Messages are sent to all members of the group, and no two messages are sent at the same time.
Immediately before a person sends a message, they read all their unread messages up to that point.
Each sender also reads their own message the moment it is sent. Therefore, a person’s unread messages are exactly the set of messages sent after that person’s last message.
Each time a message is sent, compute the total number of unread messages over all group members.
输入
The first line of input contains two integers n (1 ≤ n ≤ 109 ) and m (1 ≤ m ≤ 1,000), where n is the number of people in the group, and m is the number of messages sent. The group members are
identified by number, 1 through n.
Each of the next m lines contains a single integer s (1 ≤ s ≤ n), which is the sender of that message. These lines are in chronological order.
输出
Output m lines, each with a single integer, indicating the total number of unread messages over all group members, immediately after each message is sent.
样例输入
【样例1】
2 4
1
2
1
2
【样例2】
3 9
1
2
3
2
1
3
3
2
1
样例输出
【样例1】
1
1
1
1
【样例2】
2
3
3
4
3
3
5
4
3
题目大意:
有n个人发m次消息(每次只有一个人发),接下来m行没行输入是第几个人发的。
当一个人发消息时,其他所有人都会有一条未读消息,当一个人发消息时,他的未读消息会清0.
AC代码:
#include<bits/stdc++.h>
using namespace std;
#define CLEAR(a) memset(a,0,sizeof a);
typedef long long ll;
const int N = 1e5+5;
const ll mod = 1e9+7;
map<ll,ll> mp;
int main()
{
ll n,m,x,res=0;
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>x;
res+=(n-(i-mp[x]));
mp[x]=i;
cout<<res<<endl;
}
return 0;
}
思路:
因为发一条消息时,除了自己每个人的未读消息都会+1。那不妨假设每个人都会+1,也就是说未读消息总数+n。
然后我们再减去发消息的人已经看了的消息,用map记录上一次看消息是什么时候,用i-mp[x]就是已经看了的消息(不需要额外-1,因为A发消息时A也+1了)。
那么只要加上n-(i-mp[x])就是未读消息的量了。
边栏推荐
- nodejs爬虫
- Cost accounting [20]
- Research Report of pharmaceutical solvent industry - market status analysis and development prospect prediction
- 基于web的照片数码冲印网站
- C语言学习笔记
- Find 3-friendly Integers
- LeetCode#36. Effective Sudoku
- 信息安全-威胁检测引擎-常见规则引擎底座性能比较
- STM32 learning record: play with keys to control buzzer and led
- ucorelab3
猜你喜欢
Learning record: use STM32 external input interrupt
Record of force deduction and question brushing
ucorelab3
MATLAB综合练习:信号与系统中的应用
Learning records: serial communication and solutions to errors encountered
程序员的你,有哪些炫技的代码写法?
差分(一维,二维,三维) 蓝桥杯三体攻击
JS --- BOM details of JS (V)
VS2019初步使用
1010 things that college students majoring in it must do before graduation
随机推荐
Accounting regulations and professional ethics [3]
ucorelab3
Market trend report, technical innovation and market forecast of geosynthetic clay liner in China
Research Report on market supply and demand and strategy of China's Medical Automation Industry
Cost accounting [22]
China exterior wall cladding (EWC) market trend report, technical dynamic innovation and market forecast
0-1 knapsack problem (I)
MATLAB实例:阶跃函数的两种表达方式
入门C语言基础问答
学习记录:TIM—电容按键检测
Research Report on shell heater industry - market status analysis and development prospect forecast
mysql导入数据库报错 [Err] 1273 – Unknown collation: ‘utf8mb4_0900_ai_ci’
力扣刷题记录
LeetCode#62. Different paths
Accounting regulations and professional ethics [1]
Cost accounting [20]
C语言数组的概念
Perinatal Software Industry Research Report - market status analysis and development prospect forecast
Cost accounting [24]
Research Report of cylindrical grinder industry - market status analysis and development prospect forecast