请选择 进入手机版 | 继续访问电脑版

Good Bye 2020 B. Last minute enhancements 模拟

[复制链接]
为你演绎 发表于 2021-1-3 11:56:37 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
Athenaeus has just finished creating his latest musical composition and will present it tomorrow to the people of Athens. Unfortunately, the melody is rather dull and highly likely won’t be met with a warm reception.
His song consists of n notes, which we will treat as positive integers. The diversity of a song is the number of different notes it contains. As a patron of music, Euterpe watches over composers and guides them throughout the process of creating new melodies. She decided to help Athenaeus by changing his song to make it more diverse.
Being a minor goddess, she cannot arbitrarily change the song. Instead, for each of the n notes in the song, she can either leave it as it is or increase it by 1.
Given the song as a sequence of integers describing the notes, find out the maximal, achievable diversity.
Input
The input consists of multiple test cases. The first line contains an integer t (1≤t≤10000) — the number of test cases. Then t test cases follow, each one is described in two lines.
In the first line of each test case there is a single integer n (1≤n≤105) denoting the length of the song. The next line contains a sequence of n integers x1,x2,…,xn (1≤x1≤x2≤…≤xn≤2⋅n), describing the song.
The sum of n over all test cases does not exceed 105.
Output
For each test case, you should output a single line containing precisely one integer, the maximal diversity of the song, i.e. the maximal possible number of different elements in the final sequence.
Example
inputCopy
5
6
1 2 2 2 5 6
2
4 4
6
1 1 3 4 4 5
1
1
6
1 1 1 2 2 2
outputCopy
5
2
6
1
3
Note
In the first test case, Euterpe can increase the second, fifth and sixth element to obtain the sequence 1,3–,2,2,6–,7–, which has 5 different elements (increased elements are underlined).
In the second test case, Euterpe can increase the first element to obtain the sequence 5–,4, which has 2 different elements.
In the third test case, Euterpe can increase the second, fifth and sixth element to obtain the sequence 1,2–,3,4,5–,6–, which has 6 different elements.
元旦红包抢不外挂怎么办QAQ
和A题根本一样,只要修改重复出现的就可以
[code]#include#include#include#include#include#include#include#include#define ls (kt;    while(t--){        int n;        cin>>n;        for(int i=1;i>a;        sort(a+1,a+1+n);        mapmp;        int ans=0;        for(int i=1;i
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则


专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )