UPC - 2022春混合个人训练赛第五场 D Seahorse Shoes(贪心+模拟)

题目描述：
Mr. Hippocampus is currently pregnant with his and his wife’s baby seahorses (recall that male seahorses are the ones that carry the developing babies). Nurse Shark has recently done an ultrasound on Mr. Hippocampus and has informed Mr. and Mrs. Hippocampus exactly how many baby seahorses they will be having. Furthermore, through the help of Delphinapterus, the Beluga (and his sonar abilities), Mr. and Mrs.
Hippocampus know in advance what shoe size each of their baby seahorses will have. Thus, the newly expecting parents are preparing for their coming young and are buying all of the seahorse shoes they will need.
Seahorses, as you know, only need one shoe for their tail. However, Cobbler the Crab only sells shoes in pairs. Mr. and Mrs. Hippocampus want to get shoes for all of their baby seahorses but they want to spend the least amount of money possible. Furthermore, they do not want their children to be too uncomfortable. Thus, if a baby seahorse has a certain shoe size, he/she will only be comfortable wearing a shoe of either that size or one which is exactly one size too big or one size too small. Formally, if a baby seahorse has a shoe size of x, he/she will be comfortable wearing either a shoe of size x, (x + 1), or (x - 1). Cobbler the Crab sells shoes in all positive integer sizes and each pair of shoes costs the same amount of money. However, Cobbler the Crab only sells shoes in pairs and, thus, will not sell single shoes. Thus, Mr. and Mrs. Hippocampus may have extra shoes because they can only buy them in pairs. However, they are okay with this as long as they buy the least number of pairs of shoes possible while still assuring that each baby seahorse gets a shoe which will be comfortable for him/her to wear.

Given the number of baby seahorses Mr. and Mrs. Hippocampus are having and all of their respective shoe sizes, calculate the minimum number of pairs of shoes that Mr. and Mrs.
Hippocampus need to purchase to guarantee that each baby seahorse gets a shoe that he/she can wear comfortably (if it is either is his/her size, or is one size too big or too small).
输入：
The first line of input will contain a single, positive integer, t, representing the number of litters to follow. Following this, each litter will be contained on two lines. The first line for each litter will contain one positive integer, n (n ≤ 2,500), representing the number of baby seahorses Mr. and Mrs. Hippocampus will be having. The next line contains n positive integers representing the shoe sizes of each baby seahorse. No baby seahorse will have a shoe size which is larger than 1,000.
输出：
For each litter, output a line containing “Litter #x: m” where x is the litter number in the order given in the input (starting with 1) and m is the minimum number of pairs of shoes that Mr. and Mrs. Hippocampus need to buy for that litter.
样例输入：

2 
5 
2 3 1 1 1 
10 
4 1 9 4 1 8 9 1 8 4

样例输出：

Litter #1: 3 
Litter #2: 6

题目大意：
海马买鞋，每个海马穿一只鞋，鞋子只能成双买，每个海马的鞋子的鞋号是x,它可以穿鞋号是x,x-1,x+1的鞋,给出T组数据，每组 n 只海马，求出每组海马最少买的鞋子数。

思路：当两个海马的鞋号相差为0/1/2时可以穿一双鞋，将每组的鞋号从小到大排序，能组就组。

我们假设一双鞋的鞋号是 7 ，鞋号大小为 6，7，8的企鹅可以穿，、
有三种情况，分别是
1.鞋号相同，例如(6,6)
2.鞋号相差1，例如(6,7)
3.鞋号相差2，例如(6,8)

从鞋号的方向更容易理解这道题

代码：

#include<bits/stdc++.h>
using namespace std;
  
typedef unsigned long long ull;
typedef long long ll;
  
const ll maxx = 1e18;
const int N = 1e6+100;
const int p = 1e4;
const double eps = 1e-8;
 
int n;
int k,cnt,cnts;
 
int t;
 
priority_queue<int,vector<int>,greater<int> >pmin;
 
int main()
{
     
 
    cin>>n;
    while(n--)
    {
        cnt=0;
        cin>>k;
         
        for(int i=1;i<=k;i++)
        {
            cin>>t;
            pmin.push(t);
        }
         
        while(pmin.size()>1)//利用优先队列进行模拟，注意结束条件
        {
            int s=pmin.top();
            pmin.pop();
             
            if(pmin.top()-s<=2)
            {
                pmin.pop();
            }
            cnt++;
        }
         
        if(!pmin.empty())
        {
            pmin.pop();
            cnt++;
        }//处理队列中可能剩余的一个元素
         
        cout<<"Litter #"<<++cnts<<": "<<cnt<<endl;
         
    }
     
    return 0;
}

反思：

第一次做的时候把相差2的情况漏了，想半天也想不出来，还是问了学长才解决的，以后要多注意细节，多注意思考方式