首页 > 试题广场 >

ん...红茶?

[编程题]ん...红茶?
  • 热度指数:4191 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 128M,其他语言256M
  • 算法知识视频讲解
高贵的蕾米莉亚大小姐每天需要饮用定量 B 型血的红茶以保持威严,并且要分两杯在不同时段饮用。
女仆长十六夜咲夜每天可以制作很多杯不同剂量 B 型血的红茶供蕾米莉亚大小姐饮用。
某日,你和天才妖精琪露诺偷偷潜入红魔馆被咲夜抓住,要求在今日份的红茶中挑出所有满足大小姐要求的茶杯,否则……

输入描述:
每个样例有三行输入,第一行输入表示茶杯个数,第二行输入表示每份茶杯里的 B 型血剂量,第三行表示大小姐今天的定量


输出描述:
对每一个样例,输出所有可能的搭配方案,如果有多种方案,请按每个方案的第一杯 B 型血剂量的大小升序排列。
如果无法找到任何一种满足大小姐的方案,输出"NO"(不包括引号)并换行。
示例1

输入

7
2 4 6 1 3 5 7
7

输出

1 6
2 5
3 4

备注:
茶杯个数不超过100000,保证茶杯里的B型血剂量两两不同。
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n,t;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
        cin>>a[i];
    cin>>t;
    sort(a,a+n);
    bool flag = false;
    int l=0, r=n-1;
    while(l<r){
        if(a[l]+a[r]==t){
            cout<<a[l++]<<" "<<a[r]<<endl;
            flag = true;
        }else if(a[l]+a[r]<t)
            l++;
        else
            r--;
    }
    if(!flag)
        cout<<"NO"<<endl;
    return 0;
}

发表于 2019-10-25 00:49:07 回复(0)
input()
l = list(map(int, input().split()))
x = int(input())
l.sort()
s, flag = set(), True
for i in l: s.add(x-i)
for i in l:
    if i in s and i<x-i:
        print(i, x-i)
        flag = False
if flag: print('NO')
python真方便~~~!
发表于 2019-09-26 16:46:02 回复(0)
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] s = br.readLine().split(" ");
        int need = Integer.parseInt(br.readLine());
        int[] blood = new int[n];
        for (int i = 0; i < blood.length; i++) {
            blood[i] = Integer.parseInt(s[i]);
        }
        Arrays.sort(blood);
        int left = 0;
        int right = n - 1;
        boolean flag = false;
        while (left < right) {
            if (blood[left] + blood[right] == need) {
                flag = true;
                System.out.println(blood[left] + " " + blood[right]);
                left++;
            } else if (blood[left] + blood[right] > need) {
                right--;
            } else {
                left++;
            }
        }
        if (!flag) {
            System.out.println("NO");
        }
    }
}
编辑于 2019-08-20 16:55:54 回复(0)
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,m;
    cin>>n;
    vector<int>num(n);
    for(int i=0;i<n;i++)
        cin>>num[i];
    cin>>m;
    sort(num.begin(),num.end());
    int i=0,j=n-1,f=0;
    while(i<j)
    {
        if(num[i]+num[j]<m)
            i++;
        else if(num[i]+num[j]>m)
            j--;
        else{
            cout<<num[i]<<" "<<num[j]<<endl;
            f++;
            i++;
        }
    }
    if(f==0)
        cout<<"NO"<<endl;
    return 0;
}

发表于 2019-08-14 22:39:39 回复(0)
#include<bits/stdc++.h>
using namespace std;
int n,m,flag=0;
vector<int> v;
void erfen(int l,int r,const int &dq)
{
    if(v[l]==dq||v[r]==dq)    {cout<<m-dq<<" "<<dq<<endl;flag=1;}
    else if(r<=l)    return;
    else
    {
        if(dq>v[(r+l)/2])
            erfen((r+l)/2+1,r,dq);
        else    erfen(l,(r+l)/2,dq);
    }
}
int main()
{
    int t,zz;
    cin>>n;
    for(int i=0;i<n;i++)
        {cin>>t;v.push_back(t);}
    cin>>m;
    sort(v.begin(),v.end());
    for(int i=0;v[i]<=m/2&&i<n;i++)
    {
        int dq=m-v[i];
        erfen(i+1,n-1,dq);
    }
    if(!flag)    cout<<"NO"<<endl;
}
这题就差直接告诉你写个二分,不用优化都能AC

发表于 2022-01-14 06:39:43 回复(0)
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int count = in.nextInt();
            int[] nums = new int[count];
            for(int i = 0; i < count; i++){
                nums[i] = in.nextInt();
            }
            int target = in.nextInt();
            Arrays.sort(nums);
            //左右指针
            int left = 0;
            int right = nums.length - 1;
            StringBuilder res = new StringBuilder();
            while(left < right){
                int cur = nums[left] + nums[right];
                if(cur == target){
                    res.append(nums[left] + " " + nums[right] + "\n");
                    left++;
                    right--;
                }
                else if(cur < target){
                    left++;
                }
                else if(cur > target){
                    right--;
                }
            }
            //结果为空
            if(res.length() == 0){
                System.out.println("NO");
            }
            else{
                System.out.println(res);
            }
        }
    }
}
常规解法,排序+双指针。(就是95%后的测试用例什么情况,说不通过,但是我对比实际输出又显示一致。。
发表于 2021-01-26 13:35:14 回复(1)
let line = readline();
let n = parseInt(line);
let nums = new Array(n);
line = readline();
let lines = line.split(' ');
for(let i = 0; i < n; i++){
    nums[i] = parseInt(lines[i]);
}
line = readline();
let target = parseInt(line);
let res = [];
 
var solution = (nums, target) => {
    if(nums.length < 2) return false;
    nums.sort((a, b) => a - b);
    let i = 0, j = nums.length - 1;
    let flag = 0;
    while(i < j){
        if(nums[i] + nums[j] > target) j--;
        else if(nums[i] + nums[j] < target) i++;
        else{
            flag = 1;
            console.log(nums[i], nums[j]);
            i++;
            j--;
        } 
    }
    return flag;
}
 
if(!solution(nums, target)) console.log('NO');
常规解法,但是只能通过95%
发表于 2020-12-07 20:59:39 回复(0)
package main

import (
	"fmt"
	"sort"
)

func main() {
	n:=0
	fmt.Scan(&n)
	nums:=make([]int,n)
	for i:=0;i<n;i++{
		fmt.Scan(&nums[i])
	}
	sort.Ints(nums)
	sum:=0
	fmt.Scan(&sum)
	left,right:=0,n-1
	count:=0
	for left<right{
		if nums[left]==sum-nums[right]{
			fmt.Println(nums[left],nums[right])
			left++
			count++
		}else if nums[left]>sum-nums[right]{
			right--
		}else{
			left++
		}
	}
	if count==0{
		fmt.Println("NO")
	}
}

发表于 2020-08-18 10:17:31 回复(0)
越共探头
#include<iostream>
#include<algorithm>
using namespace std;
int search(int arr[],int low , int high, int key){
	if(low<=high){
		int mid = low + (high-low)/2;
		if(arr[mid] == key)
			return mid;
	
		else if (arr[mid] > key)
			return search(arr,low,mid-1,key);
        
        return search(arr,mid+1,high,key);  
	}
	
	return -1;
}

int main(){
	int a[100010];
	int n;
	cin>>n;
	for(int i=0;i<n;i++) cin>>a[i];
	sort(a,a+n);
	int k;
	cin>>k;
	int cnt=0;
	for(int i=0;k-a[i]>a[i];i++){
		if(search(a,i,n,k-a[i])!=-1) {
			cout<<a[i]<<" "<<k-a[i]<<endl;
			cnt++;
		}
	}
	if(cnt==0) cout<<"NO\n";
}


发表于 2020-06-26 00:52:58 回复(0)
/*
    AC=85%,麻烦各位大佬看看是啥原因?我使用的是hashmap解法
*/
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <limits.h>
#include <stack>
#include <unordered_map>
#include <map>
#include <queue>

using namespace std;

void blackTea() {
    int n, k, t, one, two;
    cin >> n;
    vector<int> vec(n);
    vector<pair<int, int>> res;
    map<int, bool> mp;
    for (int i = 0; i < n; i++)
    {
        cin>>vec[i];
        mp[vec[i]] = false;
    }
    cin >> k;
    for (int i = 0; i < n; i++)
    {
        t = k - vec[i];
        if (mp.count(t) && mp[vec[i]] == false && mp[t] == false)
        {
            one = vec[i] > t ? t : vec[i];
            two = vec[i] > t ? vec[i]: t;
            res.push_back(make_pair(one, two));
            mp[vec[i]] = true;
            mp[t] = true;
        }
    }
    //sort(res.begin(), res.end(), cmp_bt);
    sort(res.begin(), res.end(), [=](const pair<int, int> a, const pair<int, int> b) {
        return a.first < b.first;
    });
    if (res.size() > 0)
    {
        for (auto a : res)
        {
            cout << a.first << " " << a.second << endl;
        }
    }
    else
    {
        cout<< "NO" <<endl;
    }
}

int main(){
    blackTea();
	return 0;
}

发表于 2020-06-02 17:38:41 回复(0)
95%以后的测试用例有问题。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

/**
 * @Author: coderjjp
 * @Date: 2020-05-08 9:39
 * @Description: ん...红茶?
 * @version: 1.0
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.valueOf(br.readLine());
        String[] s = br.readLine().split(" ");
        int x[] = new int[n];
        for (int i = 0; i < n; i++)
            x[i] = Integer.valueOf(s[i]);
        int t = Integer.valueOf(br.readLine());
        Arrays.sort(x);
        int count = 0;
        int l = 0, r = n-1;
        while (l < r){
            if (x[l]+x[r] == t){
                count++;
                System.out.println(x[l]+" "+x[r]);
                l++;
                r--;
            }
            else if (x[l]+x[r] > t)
                r--;
            else
                l++;
        }
        if (count == 0)
            System.out.println("NO");
    }
}


发表于 2020-05-08 09:57:45 回复(0)

可处理数据重复的情况,对于4 1 1 1 1 2这样的极端情况也可以,因为枚举时用的排列组合。非极端情况如4 1 1 2 2 3这种,无需排列组合。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5;
int a[N+5];

int main(){
    int n,k;
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    scanf("%d",&k);
    if(n==1) puts("NO");
    else{
        sort(a,a+n);
        bool flag = 0;
        int start = 0, end = n-1;
        while(start<end){
            int sum = a[start]+a[end];
            if(sum==k){
                int ts = start,te = end;
                //找前一个数相同的个数
                while(start<end&&a[start]==a[start+1]) start++;
                //默认start和end对应一个数,所以组合种数为n*(n-1)/2
                int num = (start-ts+1)*(start-ts)/2;
                //两个数不同,种数为n*m
                if(start!=end){
                    while(start<end&&a[end]==a[end-1]) end--;
                    num = (start-ts+1)*(te-end+1);
                }
                for(int i=0;i<num;i++)
                    printf("%d %d\n",a[start],a[end]);
                start++;
                end--;
                flag = 1;
            }else if(sum>k) end--;
            else start++;
        }
        if(!flag) puts("NO");
    }
    return 0;
}
发表于 2020-03-21 17:59:57 回复(0)
其实不难,就是先排序,再计算和,通过指针移动罢了,但是95%之后就一直不可以了
//茶杯数(数组长度)
var num=parseInt(readline());
//剂量数组
var arr=readline().split(' ').map(Number);
// 总数
var max=parseInt(readline());
// 首先进行排序,然后判断左指针+右指针是否等于max,输出print
function funsort(a,b){
    if(a>b){
        return 1;
    }else if(a<b){
        return -1;
    }else{
        return 0;
    }
}
arr.sort(funsort)

var left=0;
var right=num-1;
// 找不到方案
var no=true;
while(true){
    if(left>=right){
        if(no){
            print('NO');//不需要 \n换行
        }
        break;
    }
    
    if(arr[left]+arr[right]==max){
        print(arr[left]+' '+arr[right])
        left++;
        right--;
        no=false;
    }
    else if(arr[left]+arr[right]<max){
        left++;
    }
    else if(arr[left]+arr[right]>max){
        right--;
    }
}

发表于 2020-02-14 18:14:25 回复(2)
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin>>n;
    vector<int> nums(n);
    for(int i=0; i<n; i++) cin>>nums[i];
    int target;
    cin>>target;
    sort(nums.begin(), nums.end());
    int p1 = 0, p2 = n-1;
    int f = 0;
    while(p1<p2)
    {
        if(nums[p1]+nums[p2]==target) cout<<nums[p1]<<" "<<nums[p2]<<endl, p1++, p2--, f++;
        else if(nums[p1]+nums[p2]>target) p2--;
        else if(nums[p1]+nums[p2]<target) p1++;
    }
    if(f==0)
    {
        cout<<"NO"<<endl;
        return 0;
    }
    return 0;
} 
请教一下 大佬们,这个双指针当找到要求的时候,是p1++, p2-- 还是p1++就可以了,不是说两两杯子的血是不同的吗,那应该p1++, p2-- 是可以的把,但是只能通过95%,希望大神们解答一下
发表于 2019-12-31 14:30:29 回复(1)
坑题
发表于 2019-09-26 11:23:40 回复(0)

参考 野径入桑麻 答案,改了判断顺序,ac100%

numCup = int(input())
doseB = list(map(int, input().split()))
doseNeed = int(input())
doseB.sort()
res_all = []
start = 0
end = numCup-1
while start < end:
    a = doseB[start]
    b = doseB[end]
    if a+b == doseNeed:
        res_all.append([a,b])    
    if a+b > doseNeed:
        end -= 1
    else:
        start +=1
if len(res_all) == 0:
    print('NO')
else:
    for item in res_all:
        print('%s %s'%(item[0],item[1]))
发表于 2019-08-20 12:49:01 回复(0)
喵喵喵,题目中虽然说明了数组中的数字是不同的。可是呢,是有相同的。所以,要想百分百pass这道题,只能在双指针的基础上加上重复检查。
import sys
input_strs = []
for line in sys.stdin:
	input_strs.append(line.strip())
cup_N = int(input_strs[0])
cup_list = []
line_1 = input_strs[1].split(" ")
for v in line_1:
	if len(v) > 0:
		if v[0] >= '0' and v[0] <= '9':
			cup_list.append(int(v))
		else:
			print("Error...")
	else:
		print("Error......")
cup_SUM = int(input_strs[2])
flag = False
cup_list.sort()
first, second = 0, cup_N - 1
if len(cup_list) != cup_N:
	print("Error1....")
# 数组中的数一定是不一样的
while first < second:
	if cup_list[first] + cup_list[second] == cup_SUM:
		# result.append([cup_list[first], cup_list[second]])
		print(str(cup_list[first]) + " " + str(cup_list[second]))
		# 针对可能重复的fisrt
		while first < second and cup_list[first] == cup_list[first + 1]:
			first += 1
			print(str(cup_list[first]) + " " + str(cup_list[second]))
			
		# 针对可能重复的second
		while first < second and cup_list[second] == cup_list[second - 1]:
			second -= 1
			print(str(cup_list[first]) + " " + str(cup_list[second]))
		flag = True
		first += 1
		second -= 1
	elif cup_list[first] + cup_list[second] < cup_SUM:
		first += 1
	else:
		second -= 1
if not flag:
	print("NO")

编辑于 2019-08-10 15:58:49 回复(1)
C++最后一组给的案例有问题
#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;
int main()
{
    int n;cin >> n;
    vector<int> vec(n,0);
    for(int i  =0 ; i< n;i++) cin >> vec[i];
    int sum; cin >> sum;
    vector<vector<int>> res;
    sort(vec.begin(), vec.end());
    int left = 0; int right = n-1;
    bool vis = false;
    while(left < right)
    {
        if(vec[left] + vec[right] == sum) 
        {
             res.push_back({vec[left],vec[right]});
            left++;
            vis = true;
        }
        else if(vec[left] + vec[right] > sum) right--;
        else if(vec[left] + vec[right] < sum) left++;
    }
    if(vis == false) 
    {
        cout << "NO" << endl; return 0;
    }
    for(int i =0 ;i < res.size();i++)
    {
        cout << res[i][0] << " " << res[i][1] << endl;
    }
    return 0;
}


发表于 2019-08-06 21:17:36 回复(0)
双指针,c++,只过95%的用例。不知出了什么问题
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e5+10;
int a[N];

int main()
{
    int n;
    cin >> n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    int m;
    cin>>m;
    sort(a,a+n);
    int *p = &a[0];
    int *q = &a[n-1];
    int cnt = 0;
    while(*q > m)
        q--;
    while(p<q)
    {
        if(*p+*q == m)
        {
            cout<<*p<<' '<<*q<<endl;
            cnt++,p++,q--;
        }
        else if(*p+*q > m)
            q--;
        else if(*p+*(p+1) > m)
            break;
        else
            p++;
    }
    if(!cnt)
        cout<<"NO"<<endl;
    return 0;
}

发表于 2019-07-17 15:34:01 回复(1)

感觉双指针应该没问题,但是95%,看到备注
茶杯个数不超过100000,保证茶杯里的B型血剂量两两不同。
然后没过的用例:
用例:
100000

200000 200000 200003 ...,两个200000,说好的两两不同呢?
最终相同的时候不能同时移动指针,移动低位即可。
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int cups = sc.nextInt();
        sc.nextLine();
        String line = sc.nextLine();
        int target = sc.nextInt();
        sc.close();

        int[] vols = Arrays.stream(line.split(" ")).mapToInt(Integer::parseInt).toArray();
        Arrays.sort(vols);

        int s = 0, e = vols.length - 1;
        boolean find = false;
        while (s < e) {
            int firstCup = vols[s], secondCup = vols[e];
            if (firstCup + secondCup == target) {
                System.out.printf("%d %d\n", firstCup, secondCup);
                find = true;
                ++s;
            } else if (firstCup + secondCup > target) {
                --e;
            } else {
                ++s;
            }
        }

        if (!find) {
            System.out.println("NO");
        }
    }
}
编辑于 2019-07-16 22:35:46 回复(0)

热门推荐

通过挑战的用户

查看代码