当前位置:网站首页>[exercise -10] unread messages
[exercise -10] unread messages
2022-07-06 15:57:00 【Flame car】
Title Description
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.
Input
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
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.
The sample input
【 Examples 1】
2 4
1
2
1
2
【 Examples 2】
3 9
1
2
3
2
1
3
3
2
1
Sample output
【 Examples 1】
1
1
1
1
【 Examples 2】
2
3
3
4
3
3
5
4
3
The main idea of the topic :
Yes n Personal hair m The second news ( Only one person at a time ), Next m Line no line input is sent by the first person .
When a person sends a message , Everyone else will have an unread message , When a person sends a message , His unread news will be cleared 0.
AC Code :
#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;
}
Ideas :
Because when sending a message , Everyone's unread messages except myself will +1. Let's assume that everyone will +1, That is, the total number of unread messages +n.
Then we subtract the message that the sender has read , use map Record the last time you read the message , use i-mp[x] It's the news that I've read ( No extra -1, because A When sending messages A also +1 了 ).
Then just add n-(i-mp[x]) Is the amount of unread messages .
边栏推荐
- Learning record: how to perform PWM output
- 0-1 knapsack problem (I)
- China earth moving machinery market trend report, technical dynamic innovation and market forecast
- 渗透测试 ( 4 ) --- Meterpreter 命令详解
- 渗透测试 ( 8 ) --- Burp Suite Pro 官方文档
- Accounting regulations and professional ethics [1]
- [exercise-6] (PTA) divide and conquer
- B - 代码派对(女生赛)
- Web based photo digital printing website
- Cost accounting [21]
猜你喜欢
渗透测试 ( 4 ) --- Meterpreter 命令详解
信息安全-安全编排自动化与响应 (SOAR) 技术解析
力扣刷题记录
数据在内存中的存储&载入内存,让程序运行起来
Ball Dropping
Learning record: Tim - Basic timer
【练习-7】Crossword Answers
Penetration test (3) -- Metasploit framework (MSF)
Learning records: serial communication and solutions to errors encountered
D - Function(HDU - 6546)女生赛
随机推荐
[exercise-2] (UVA 712) s-trees
VS2019初步使用
CS zero foundation introductory learning record
Matlab example: two expressions of step function
China's earthwork equipment market trend report, technical dynamic innovation and market forecast
初入Redis
TCP的三次握手与四次挥手
Optimization method of path problem before dynamic planning
Research Report on market supply and demand and strategy of China's land incineration plant industry
Find 3-friendly Integers
Opencv learning log 12 binarization of Otsu method
入门C语言基础问答
Penetration test (3) -- Metasploit framework (MSF)
Research Report of exterior wall insulation system (ewis) industry - market status analysis and development prospect prediction
Opencv learning log 19 skin grinding
0-1背包问题(一)
C 基本语法
Cost accounting [14]
基于web的照片数码冲印网站
Cost accounting [13]