当前位置:网站首页>【练习-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])就是未读消息的量了。
边栏推荐
猜你喜欢
Learning record: STM32F103 clock system overview working principle
Ball Dropping
STM32學習記錄:輸入捕獲應用
ucorelab3
JS --- detailed explanation of JS DOM (IV)
学习记录:USART—串口通讯
STM32学习记录:输入捕获应用
LeetCode#36. Effective Sudoku
JS --- detailed explanation of JS facing objects (VI)
mysql导入数据库报错 [Err] 1273 – Unknown collation: ‘utf8mb4_0900_ai_ci’
随机推荐
Accounting regulations and professional ethics [2]
C语言数组的概念
Cost accounting [14]
通俗地理解什么是编程语言
信息安全-威胁检测-NAT日志接入威胁检测平台详细设计
STM32学习记录:输入捕获应用
MATLAB综合练习:信号与系统中的应用
基于web的照片数码冲印网站
Research Report on medical toilet industry - market status analysis and development prospect forecast
Path problem before dynamic planning
C语言学习笔记
Cost accounting [20]
用C语言写网页游戏
HDU-6025-Coprime Sequence(女生赛)
SSM框架常用配置文件
学习记录:理解 SysTick系统定时器,编写延时函数
Learning record: USART serial communication
cs零基础入门学习记录
FSM and I2C experiment report
0-1背包问题(一)