ECNU机试之判断“东西越贵越好”的命题

由于题目比较长，并且时间已久，我只记得题目大概的意思：给出N个商品的价格和质量，判断“东西越贵越好”这个命题是否正确。

Input

第1行，一个数N，N为商品的数量。(2 <= N <=100)

第2 - N + 1行：具体N个商品的价格和质量。

Output

判断是否符合“东西越贵越好”这个命题，输出yes/no。

Input示例

6
1 2
3 5
4 8
6 9
10 13
15 18

5
1 3
3 6
5 8
6 7
7 10

Output示例

yes

no

解题思想：与求最大斜率那题类似，将商品按价格排序，对比相邻两个商品的质量，判断是否存在“价格变高，质量却降低”的情况。

参考代码（没有用STL）：

#include <iostream>

using std::cin;
using std::cout;
using std::endl;

struct node //存储商品的信息
{
    float x,y;
};

int main()
{
    bool flag=true;
    int n=0;
    while(cin>>n)
    {
        node nodes[50];

        for(int i=0; i<n; i++)
        {
            cin>>nodes[i].x>>nodes[i].y;
        }

        for(int i=n; i>0; i--)//商品按价格排序
        {
            for(int i=0; i+1<n; i++)
            {
                if(nodes[i].x>nodes[i+1].x)
                {
                    node temp;
                    temp=nodes[i];
                    nodes[i]=nodes[i+1];
                    nodes[i+1]=temp;
                }
            }
        }

        for(int i=1; i<n; i++)//遍历价格相近商品的质量
        {
            if(nodes[i].y-nodes[i-1].y<=0)//寻找是否存在价格高的商品质量却比价格低的差
            {
                flag=false;
                break;
            }
        }

        if(flag==true)//输出结果
        {
            cout<<"yes"<<endl;
        }
        else cout<<"no"<<endl;

    }
    return 0;
}