题解：CF1957A Stickogon

volatile · 2024-05-03 21:10:51 · 题解

思路

首先看样例

4
1
1
2
1 1
6
2 2 3 3 3 3
9
4 2 2 2 2 4 2 4 4

首先可以肯定当 t 为 1 和 2 时不能组成多边形，易知要组成最多的多边形，三角形更有性价比，观察样例 t 为 6 可以发现，只要用相同的木棍除以 3 取整便是答案，可能会有人问了，那我用 2,3,3 不就有 2 种了吗？刚开始我也这么想，但题目说了，是正多边形，所以只需考虑相同木棍，用桶即可。

代码

#include<iostream>
#include<string.h>
using namespace std;
int a[114];
int main()
{
    int n;
    cin>>n;
    while(n--){
        int t,sum=0;
        cin>>t;
        memset(a,0,sizeof(a));//注意清零
        while(t--){
            int x;
            cin>>x;
            a[x]++;
        }
        for(int i=1;i<=100;i++) sum+=a[i]/3;
        cout<<sum<<endl;
    }
    return 0;
}