首页 > > 程序设计 > C/C++ >

『ACM C++』Virtual Judge | 两道基础题 - The A…

2019-02-25 16:09:29来源：博客园阅读 ()

　　这几天一直在宿舍跑PY模型，学校的ACM寒假集训我也没去成，来学校的时候已经18号了，突然加进去也就上一天然后排位赛了，没学什么就去打怕是要被虐成渣，今天开学前一天，看到最后有一场大的排位赛，就上去试了一下，果然被虐成渣，十二道题目在有限时间内就做了四道，还有一道疯狂的WA，拿出两道一些有趣的想法出来分享一下。

　　今天打题就遇到了大数计算的问题，本来昨晚想解决这个难题，也没来得及，所以打题的时候大数计算那道就放弃了，过几天我一定会扔上来的。

今日兴趣新闻：

年度最惨小学生！在姥姥家热炕头写作业，写完一看字都没了！

https://baijiahao.baidu.com/s?id=1625958926368259758&wfr=spider&for=pc

笑出猪叫声，正映衬现在刚开学前的大学生疯狂的恶补一些零零碎碎的作业和策划书哈哈，话说这个热可擦我也还没玩过呢，老了老了。

------------------------------------------------题目----------------------------------------------------------

Malek and Summer Semester

Malek registered n courses for the summer semester. Malek has a success rate m, which means he has to succeed at least in ceil(n × m) courses out of the n courses, in order to consider the summer semester as a successful semester. Malek is considered successful in the i^th course, if his grade on this course was greater than or equal to 50.

ceil(x) is the smallest integer greater than or equal to x. For example, ceil(0.95) = 1, ceil(4) = 4, and ceil(7.001) = 8.

Malek will give you his grades in the n courses, and your task is to tell him whether the summer semester was a successful semester or not.

Input

The first line contains an integer T (1 ≤ T ≤ 100), where T is the number of test cases.

The first line of each test case contains an integer n and a real number m (1 ≤ n ≤ 100) (0 < m < 1), where n is the number of courses, and m is the required success rate.

The second line contains n integers a₁, a₂, ..., a_n (0 ≤ a_i ≤ 100), where a_i is the grade of the i^th course.

The success rate m is given with exactly two digits after the decimal point.

Output

For each test case, print a single line containing "YES" (without quotes), if the summer semester was a successful semester for Malek. Otherwise, print "NO" (without quotes).

Example

input

2
5 0.60
45 46 48 48 50
5 0.75
100 99 98 97 100

output

NO
YES

------------------------------------------------题目----------------------------------------------------------

（一）原题大意：

　　　　Malek 为夏季学期注册了n门课程。马利克拥有成功率米，这意味着他至少在成功小区（ñ × 米）课程出的ñ课程，为了考虑夏季学期作为一个成功的学期。马利克被认为是成功的我^个当然，如果他对这个课程成绩大于或等于50。

　　　　ceil（x）是大于或等于 x的最小整数。例如， ceil（0.95）= 1， ceil（4）= 4，ceil（7.001）= 8。

　　　　题目很简单，实际上这是一道2017 JUST编程大赛3.0的签到题，拿这道题出来呢是有一个小的细节使用知识点，那就是ceil

（二） AC代码：

#include<iostream>
#include<cmath>
#include<stdio.h>
using namespace std;
int times,number,mark,ok;
float up;
int main()
{
    scanf("%d", &times);
    for(;times>0;times--) 
    {
        scanf("%d %f", &number,&up);
        ok = ceil(number*up);
        printf("%d",ok);
        for(;number>0;number--)
        {
            scanf("%d", &mark);
            if(mark>=50) ok--;
        } 
        if(ok <= 0) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
 }

（三）解后分析：

　　　　这道题难度小，如果会用ceil这个函数就特别简单了，ceil(x)这个函数是向上取整函数，如果需要向下取整，还有一个函数是floor(x)。

　　　　floor()是向负无穷大舍入，floor(-10.5) == -11；
　　　　ceil()是向正无穷大舍入，ceil(-10.5) == -10

　　　　这是一个细节知识点，可能以后会经常用到呢。

------------------------------------------------题目----------------------------------------------------------

The Architect Omar

Architect Omar is responsible for furnishing the new apartments after completion of its construction. Omar has a set of living room furniture, a set of kitchen furniture, and a set of bedroom furniture, from different manufacturers.

In order to furnish an apartment, Omar needs a living room furniture, a kitchen furniture, and two bedroom furniture, regardless the manufacturer company.

You are given a list of furniture Omar owns, your task is to find the maximum number of apartments that can be furnished by Omar.

Input

The first line contains an integer T (1 ≤ T ≤ 100), where T is the number of test cases.

The first line of each test case contains an integer n (1 ≤ n ≤ 1000), where n is the number of available furniture from all types. Then n lines follow, each line contains a string s representing the name of a furniture.

Each string s begins with the furniture's type, then followed by the manufacturer's name. The furniture's type can be:

bed, which means that the furniture's type is bedroom.
kitchen, which means that the furniture's type is kitchen.
living, which means that the furniture's type is living room.

All strings are non-empty consisting of lowercase and uppercase English letters, and digits. The length of each of these strings does not exceed 50 characters.

Output

For each test case, print a single integer that represents the maximum number of apartments that can be furnished by Omar

Example

Input

1
6
bedXs
kitchenSS1
kitchen2
bedXs
living12
livingh

Output

------------------------------------------------题目----------------------------------------------------------

（一）原题大意：

　　　　这道题呢难度也不大，算是签到题，只是有点好玩。原题意思是某个人要建一个公寓，现在需要两张床bed、一个厨房kitchen、一个居室living，才能算是一个公寓，现在给你一堆家居，自带类型＋乱七八糟的字符串，让你识别出是什么类型的家具，然后输出可以组成几间公寓。

（二）题目分析：

　　　　唯一难点可能就是在识别输入的字符串中是否含有某个词语，解题后我翻了一下网上的一些做法，有人干脆就直接判断第0下标的字母'b' 'k' 'l'来区分，感觉这是不严谨的，，还有人用到了string的find函数，这个倒是挺新奇，我还不知道，待会也贴上来学习一下。我的题目做法呢是用strncmp函数，去对比开头是否是所要求的类型，然后再进行计算。打题的时候还发现一些比较有趣的字符串处理函数，如strrev(array);这是反转字符串，等等。

（三）代码分块：

　　　　第一步：先去获取到每一个家具的类型：

        for(;number>0;number--)
        {
            scanf("%s", name);
            if(strncmp(name,"bed",3) == 0) have[0]++;
            else if(strncmp(name,"kitchen",7) == 0) have[1]++;
            else if(strncmp(name,"living",6) == 0) have[2]++;
        }

　　　　我是这么做的，对比前面字母是否相同，然后获取。

　　　　第二步，计算最大拥有几个公寓：

        while(1)
        {
            if(have[0] < 2 || have[1] == 0 || have[2] == 0) break;
            have[0]-=2;
            have[1]--;
            have[2]--;
            ok++;
        }

（四） AC代码：

#include<iostream>
#include<cstring>
#include<stdio.h>
using namespace std;
int times,number,have[3],ok;
char name[51];
float up;
int main()
{
    scanf("%d", &times);
    for(;times>0;times--) 
    {
        have[0] = have[1] = have[2] = ok = 0;
        scanf("%d %f", &number);
        for(;number>0;number--)
        {
            scanf("%s", name);
            if(strncmp(name,"bed",3) == 0) have[0]++;
            else if(strncmp(name,"kitchen",7) == 0) have[1]++;
            else if(strncmp(name,"living",6) == 0) have[2]++;
        } 
        while(1)
        {
            if(have[0] < 2 || have[1] == 0 || have[2] == 0) break;
            have[0]-=2;
            have[1]--;
            have[2]--;
            ok++;
        }
        printf("%d",ok);
    }
    return 0;
 }

（五）AC截图：

（六）解后分析：

　　　　题目不难，直接判断首字母也能过，翻看别人的题解的时候发现一个string的某个用法，可能感觉挺有用，贴出来学习一下：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cmath>
using namespace std;
int main(){
    int t,n;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        int num1=0,num2=0,num3=0;
        for(int i=0;i<n;i++){
            string s;
            cin>>s;
            if(s.find("bed")==0)num1++;
            if(s.find("kitchen")==0)num2++;
            if(s.find("living")==0)num3++;
        }
        //cout<<num1<<" "<<num2<<" "<<num3<<endl;
        int ans=min(num1/2,min(num2,num3));
        printf("%d\n",ans);
    }
    return 0;
}

　　　　该题解使用了string类，并使用了string的find函数，这个函数可以查找字符串中特定的字符串内容。为了拓展这个知识点，我还找到了下面一些有趣的函数原型：

　　　　注：以下所讲的所有的string查找函数，都有唯一的返回类型，那就是size_type，即一个无符号整数（按打印出来的算）。若查找成功，返回按查找规则找到的第一个字符或子串的位置；若查找失败，返回npos，即-1（打印出来为4294967295）。

　　　　（1）find()：

//string (1)
size_type find (const basic_string& str, size_type pos = 0) const noexcept;
//c-string (2)
size_type find (const charT* s, size_type pos = 0) const;
//buffer (3)
size_type find (const charT* s, size_type pos, size_type n) const;
//character (4)
size_type find (charT c, size_type pos = 0) const noexcept;

　　　　这个也就是上面代码所使用了的了，后面的参数可以省略。

　　　　（2）rfind()：

//string (1)
size_type rfind (const basic_string& str, size_type pos = npos) const noexcept;
//c-string (2)
size_type rfind (const charT* s, size_type pos = npos) const;
//buffer (3)
size_type rfind (const charT* s, size_type pos, size_type n) const;
//character (4)
size_type rfind (charT c, size_type pos = npos) const noexcept;

　　　　 rfind()与find()很相似，差别在于查找顺序不一样，rfind()是从指定位置起向前查找，直到串首。例如，上例中的st1.rfind('a',7)一句，就是从st1的位置7（st1的最后一个字符b）开始查找字符a，第一次找到的是倒数第2个字符a，所以返回6。

　　　　（3）find_first_of()：

//string (1)
size_type find_first_of (const basic_string& str, size_type pos = 0) const noexcept;
//c-string (2)
size_type find_first_of (const charT* s, size_type pos = 0) const;
//buffer (3)
size_type find_first_of (const charT* s, size_type pos, size_type n) const;
//character (4)
size_type find_first_of (charT c, size_type pos = 0) const noexcept;

　　　　在源串中从位置pos起往后查找，只要在源串中遇到一个字符，该字符与目标串中任意一个字符相同，就停止查找，返回该字符在源串中的位置；若匹配失败，返回npos。

　　　　（4） find_last_of()：

//string (1)
size_type find_last_of (const basic_string& str, size_type pos = npos) const noexcept;
//c-string (2)
size_type find_last_of (const charT* s, size_type pos = npos) const;
//buffer (3)
size_type find_last_of (const charT* s, size_type pos, size_type n) const;
//character (4)
size_type find_last_of (charT c, size_type pos = npos) const noexcept;

　　　　该函数与find_first_of()函数相似，只不过查找顺序是从指定位置向前。

　　　　（5）find_first_not_of()：

//string (1)
size_type find_first_not_of (const basic_string& str, size_type pos = 0) const noexcept;
//c-string (2)
size_type find_first_not_of (const charT* s, size_type pos = 0) const;
//buffer (3)
size_type find_first_not_of (const charT* s, size_type pos, size_type n) const;
//character(4)
size_type find_first_not_of (charT c, size_type pos = 0) const noexcept;