基础算法-枚举

黯然 / 90 /

ChatGPT 可用网址,仅供交流学习使用,如对您有所帮助,请收藏并推荐给需要的朋友。
https://ckai.xyz

MT2001

你有n个数,可以将它们两两匹配(即将两数首尾相连),每个数只能使用一次,问匹配后最多有多少个3的倍数(没有进行匹配的数不算)?

输入格式:第一行一个n,接下来输入n个正整数
输出格式:输出最多有多少个3的倍数
输入:
3
123 123 99
输出:
1

解:任意一个正整数对3取余有三种可能,分别是0,1,2;
123%3=0 123%3=0 99%3=0,所以组合情况有123123 12399 12399,由题意可知不能重 复使用每一个数,所以只有一种可能,即在123123 12399二选一

当输入数为 4 5 7 8 10:

4%3=1 5%3=2 7%3=1 8%3=2 10%3=1,对于对3取余的数为1 or 2时,余数为1和余数为2的数组合,才能是3的倍数,又因为不能重复,所以记%3=1的数有y个,%3=2的数有Z个,所以min(y,z)y与z的最小值是能组成不重复数的最大数

#include<bits/stdc++.h> 
using namespace std;
int n,m;

int main( )
{
    cin>>n;
    int x=0,y=0,z=0;
    for(int i=0;i<n;i++)
    {
        cin>>m;
        if(m%3==0)
            x++;
        else if(m%3==1)
            y++;
        else
            z++;
    }
  cout<<x/2+min(y,z);   
  


    return 0;
}

作者
黯然
许可协议
CC BY 4.0
发布于
2023-09-24
修改于
2024-07-14
Bonnie image
尚未登录