首页 > 试题广场 >

彩色袜子

[编程题]彩色袜子

热度指数：1193 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

在衣柜抽屉中杂乱无章地放着 $\mathit n$ 种不同颜色的袜子，其中第 $\mathit i$ 种颜色的袜子有 $a_i$ 只。小招喵现在正着急去参加一场宴会，但是小招喵是一个色盲，所以无法分辨自己将要穿的袜子是不是同一颜色的，因此他随手抓了一把袜子，打算带到牛牛家让牛牛帮忙。
现在的问题是，最少要从抽屉中取出多少只袜子才能保证其中一定有两只可以配成颜色相同的一双？

输入描述:

第一行一个数字表示测试数据的组数。
对于每组数据，第一行数字表示袜子的颜色种数。
第二行有个数字，第个数字表示第种颜色的袜子有个。

输出描述:

对于每组数据，输出一行一个数字表示答案。若无解输出 -1。

示例1

输入

输出

3
-1

算法知识视频讲解

Python

pein531

数学

如果数量最多的袜子都没有凑成一双就返回-1；否则就统计有多少种袜子的数量是非零的，返回“非零袜子的种数+1”即可，因为运气最差的情况就是每种袜子都拿了一只，此时如果再拿一只袜子，肯定就能有两只袜子颜色相同，从而凑出一双。

T = int(input())
while T:
    n = int(input())
    arr = list(map(int, input().split()))
    ma = max(arr)
    if ma < 2:
        print(-1)
    else:
        cnt = 0
        for num in arr:
            if num != 0:
                cnt += 1
        print(cnt + 1)
    T -= 1

发表于 2022-04-06 20:30:49 回复(0)

斯沃福德

求至少多少袜子能凑出一对，即每种颜色的袜子各一只时，再加1只就能凑出一双！
如：2 2 1 ，则只需要3+1=4只就能凑出一双；

但如果每种颜色的袜子只有一只或者0只，再多颜色的袜子也凑不出一双！
如：1 1 1 0 1 ，怎么凑都不行，返回-1；

所以，至少要有一种袜子的颜色要大于1只！

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        int T=in.nextInt();
        for(int t=0;t<T;t++){ // 遍历不同测试数据
                // 数组长度
            int n=in.nextInt();
            int[] color=new int[n];
            int single=0;
            int num=0;
            for(int i=0;i<n;i++){
                int temp=in.nextInt();
                color[i]=temp;
                // 每种颜色取一个就是num
                // 若为单数则不算入num
                if(color[i]>1){
                    single++;
                    num++;
                }else if(color[i]==1){ // 
                    num++;
                }
            }
            if(single==0){ // 即每种颜色都是一只或0 只，则无法凑一双    
                System.out.println(-1);
            }else{
                System.out.println(num+1);
            }    
        }
    }
}

发表于 2022-08-09 17:44:20 回复(0)

kyzheng

Python版本，AK

n = int(input())
list1 = []
list2 = []

for i in range(n):
    list1.append(list(map(int, input().split())))
    list2.append(list(map(int, input().split())))

for i in range(n):
    num = 0
    if max(list2[i]) <= 1:
        print(-1)
    elif max(list2[i]) >= 2:
        for j in list2[i]:
            if j > 0:
                num += 1
        print(num+1)

发表于 2022-04-20 21:43:06 回复(0)

六月流星Y

nums = int(input())
for i in range(nums):

num = int(input())

list_1 = list(map(int,input().split()))
min_num = 0
if max(list_1)<=1:
print(-1)
else:
for i in range (len(list_1)):
if list_1[i]>0:
min_num += 1
print(min_num+1)

发表于 2022-07-03 19:18:17 回复(0)

4fbd81e

t=int(input())
while t:
    t=t-1
    n=int(input())
    a=list(map(int,input().split()))
    if (max(a)<=1) :
        print(-1)
    else:
        ret=0
        for i in a:
            if i!=0:
                ret=ret+1
        print(ret+1)

发表于 2022-04-14 15:15:51 回复(0)

半事无意

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

function findminsocks(socks){
    let single = 0
    let minnum = 0
    for(let i=0;i<socks.length;i++){
        if(socks[i]>1){
            single++
            minnum++
        }else if(socks[i]===1){
            minnum++
        }
    }
    if(single===0){
        console.log(-1)
    }else{
        console.log(minnum+1)
    }
}


void async function () {
    // Write your code here
    line = await readline()
    while(line){
       var types = await readline()
       var sock  = await readline()
       var socks = sock.split(' ').map(Number)
       findminsocks(socks)
       line--
    }
    
}()

JS实现如上

编辑于 2023-09-04 15:03:11 回复(0)

ccchloe_666

这个题主要有两个关键点：

1、一组袜子颜色中，最多颜色的袜子数小于等于1的话，是怎么都不可能凑够一双的。

2、排除了上述1的情况后，只要拿的袜子数量比一组中袜子数量不为零的个数多一个就可以了。（这个就有点像组合数学中的抽屉原理）

希望我真的表述清楚了（已经很努力在说清楚了，希望能帮到一些人理解~）哈哈哈

        // 优化前的版本
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();// T为测试数据组数
        for (int i = 0 ; i < T ; i ++){
            int n = in.nextInt();// n是袜子颜色的种类数
            int[] arr = new int[n]; // 某种颜色的袜子数量
            for (int j = 0 ; j < n ; j ++){
                arr[j] = in.nextInt();
            }
            // arr从小到大排序，最大值<=1则返回-1。否则返回种类数n中不为零的颜色种类数+1
            Arrays.sort(arr);
            if (arr[n-1] <= 1)
                System.out.println(-1);
            else
                // 这里应该遍历arr，统计元素不为零的个数count，然后输出count+1。但我觉得前面排序就花了一部分时间了，再从头遍历统计的话太耗时了。就开始想怎么优化。
                System.out.println(n+1);
        }
    }

    // 最后优化过的版本
    public void success() {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();// T为测试数据组数
        for (int i = 0; i < T; i++) {
            int n = in.nextInt();// n是袜子颜色的种类数
            int max = 0;    // 一组袜子中的最大值。是判断能不能成双的关键！max<=1直接返回-1
            int nonZeroCount = 0; // 记录一组袜子中颜色不为零的数量
            for (int j = 0; j < n; j++) {
                int input = in.nextInt();
                max = Math.max(max, input);
                if (input != 0) {
                    nonZeroCount++;
                }
            }
            if (max <= 1)
                System.out.println(-1);
            else
                System.out.println(nonZeroCount + 1);
        }
    }

发表于 2023-07-14 14:30:59 回复(0)

Java

疾风客

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        
        int T = in.nextInt();
        for(int i=0;i<T;i++){
            int kind = in.nextInt();
            int count = 0;//jizhong
            int flag = 0;//youmeiyou >2
            int[] color = new int[kind];
            for(int j=0;j<kind;j++){
                color[j] = in.nextInt();
                if(color[j]!=0){
                    count++;
                    if(color[j]>=2)
                        flag++;
                }
                    
            }
            if(count==0)
                System.out.println(-1);
            else if(count>0&&flag==0)
                System.out.println(-1);
            else
                System.out.println(count+1);
        }
    }
}

发表于 2023-05-08 10:54:18 回复(0)

crcrcrc

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int T;
    cin >> T;
    while(T--){
        int n;
        cin >> n;
        int num;
        int ans = 0;
        int num_1 = 0;
        for(int i = 0; i < n; i++){
            cin >> num;
            if(num == 1) num_1++;
            if(num >= 1) ans++;
        }
        if(ans == num_1) cout << -1 << endl;
        else cout << ans+1 << endl;
    }
}

发表于 2023-04-09 10:37:22 回复(0)

Sparklelu

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});
const inputArr = [];//存放输入的数据
let flag = 0;
rl.on('line', function(line){
  //line是输入的每一行，为字符串格式
    inputArr.push(line.split(' ').map(item=>parseInt(item)));//将输入流保存到inputArr中（注意为字符串数组）
    if(flag === inputArr[0][0]  * 2){
        rl.close()
    }
    flag++
}).on('close', function(){
    fun(inputArr);
})

//解决函数
function fun(arr) {
	let zushu = arr[0][0]
    let start = 2
    let count = 0
    while(zushu--){
        let max = Math.max.apply(null,arr[start])&nbs***bsp;let max = Math.max(...arr[start])
        if(max>1){
            for(let i=0;i<arr[start].length;i++){
                if(arr[start][i]!==0){
                    count++
                }
            }
            console.log(++count)
            count = 0
        }else{
            console.log(-1)
        }
        start = start+2
    }
}

发表于 2022-09-20 15:53:49 回复(1)

wonderson

1. 至少有一种大于1个；

2. 全部有袜子的种类数1加一

    //import java.util.*;
    public class Main {
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int T = sc.nextInt();
            for (int i = 0; i < T; i++) {
                int n = sc.nextInt();
                int cnt = 0;
                boolean hasTwo = false;
                for (int j = 0; j < n; j++) {
                    int cur = sc.nextInt();
                    if (cur > 0) {
                        cnt++;
                        if (cur > 1) {
                            hasTwo = true;
                        }
                    }
                }
                if (cnt == 0 || !hasTwo) {
                    System.out.println(-1); 
                } else {
                    System.out.println(cnt + 1);
                }
            }
            sc.close();
        }
    }

发表于 2022-08-11 21:49:03 回复(0)

啥时候能摆脱0offer

import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        for(int i = 0; i < T; i++){
            int numLength = in.nextInt();
            int count = 0;
            int flag = 0;
            int tmp = 0;
            for(int j=0; j < numLength; j++){
                int a = in.nextInt();
                              //至少有一个颜色的数量大于2才有可能得到一双
                flag = a>=2?(flag+1):flag;
                count = a>0?(count+1):count;
            }
            tmp = (count>0 && flag > 0 )?(count+1):-1;
            System.out.println(tmp);
        }
    
    
    }
}

发表于 2022-08-02 15:32:52 回复(0)