codeforce 1478A A. Nezzar and Colorful Balls 额？模拟 C

codeforce 1478A A. Nezzar and Colorful Balls 额？模拟 C

https://codeforces.com/contest/1478/problem/A.

A. Nezzar and Colorful Balls time limit per test 1 second memory limit per test 512 megabytes input standard input output standard output

Nezzar has n">nn balls, numbered with integers 1,2,…,n">1,2,…,n1,2,…,n. Numbers a1,a2,…,an">a1,a2,…,ana1,a2,…,an are written on them, respectively. Numbers on those balls form a non-decreasing sequence, which means that ai≤ai+1">ai≤ai+1ai≤ai+1 for all 1≤i<n">1≤i<n1≤i

Nezzar wants to color the balls using the minimum number of colors, such that the following holds.

  • For any color, numbers on balls will form a strictly increasing sequence if he keeps balls with this chosen color and discards all other balls.

Note that a sequence with the length at most 1">11 is considered as a strictly increasing sequence.

Please help Nezzar determine the minimum number of colors.

Input

The first line contains a single integer t">tt (1≤t≤100">1≤t≤1001≤t≤100) — the number of testcases.

The first line of each test case contains a single integer n">nn (1≤n≤100">1≤n≤1001≤n≤100).

The second line of each test case contains n">nn integers a1,a2,…,an">a1,a2,…,ana1,a2,…,an (1≤ai≤n">1≤ai≤n1≤ai≤n). It is guaranteed that a1≤a2≤…≤an">a1≤a2≤…≤ana1≤a2≤…≤an.

Output

For each test case, output the minimum number of colors Nezzar can use.

Example input Copy 
5
6
1 1 1 2 3 4
5
1 1 2 2 3
4
2 2 2 2
3
1 2 3
1
1
output Copy 
3
2
4
1
1
Note

Let's match each color with some numbers. Then:

In the first test case, one optimal color assignment is [1,2,3,3,2,1]">[1,2,3,3,2,1][1,2,3,3,2,1].

In the second test case, one optimal color assignment is [1,2,1,2,1]">[1,2,1,2,1][1,2,1,2,1].

 分析

题目要找到任意的数据都可以形成严格的上升序列

那么当一个数字重复出现的时候，一定要分配到一个数组里

就看看所有数字最多重复出现了多少次就可以了

代码

 https://codeforces.com/contest/1478/submission/105679337

#include 
#include 
#include 
#include 
#include 
#include <string.h>
#include 
#include 
#include <string>
#include 
#include 
#include 
#include 
#include 
#include 
#include <set>
#include 
#include 
#include <string.h>
#include 
#define sf scanf
#define pf printf
#define lf double
#define p123 printf("123\n");
#define pn printf("\n");
#define pk printf(" ");
#define p(n) printf("%d",n);
#define pln(n) printf("%d\n",n);
#define s(n) scanf("%d",&n);
#define ss(n) scanf("%s",n);
#define ps(n) printf("%s",n);
#define sld(n) scanf("%lld",&n);
#define pld(n) printf("%lld",n);
#define slf(n) scanf("%lf",&n);
#define plf(n) printf("%lf",n);
#define sc(n) scanf("%c",&n);
#define pc(n) printf("%c",n);
#define gc getchar();
#define ll long long
#define re(n,a) memset(n,a,sizeof(n));
#define len(a) strlen(a)
#define eps 1e-13
#define zero(x) (((x) > 0? (x):(-x)) < eps)
using namespace std;
int a[2005];
int b[2005];
int main(){
    int t;
    s(t)
    while(t --){
        int n;
        s(n)
        for(int i = 0; i < n; i ++){
            s(a[i])
        }
        sort(a,a+n);
        int maxi = 0;
        int temp = 1;
        for(int i = 1; i < n; i ++){
            if(a[i] == a[i-1]){
                temp ++;
            }else{
                maxi = max(maxi,temp);
                temp = 1;
            }
        }
        maxi = max(maxi,temp);
        p(maxi) pn
    }
    return 0;
}
ACM

相关

acm讲解

「acmhdu - 6314」Matrix

第十三届河南省ACM-ICPC游记

ACM模板

Hyperf 接入阿里云ACM应用配置管理中心

[ACM] BFS & 双端BFS & A* & 双边BFS

计算几何 / Geometry（ACM-Template 2.0）

ACM入门方式

Linux 下使用 acme.sh 配置 Let's Encrypt 免费 SSL 证书 + 通配符证书

如何写好一篇高质量的IEEE/ACM Transaction级别的计算机科学论文?

ACM- java在acm中的快速读入，多组读入，快速输出模板

ACM - 动态规划 - P1282 多米诺骨牌

标签