首页 > ACM题库 > HDU-杭电 > Hdu 1897 SnowWolf’s Wine Shop[解题报告] C++
2013
12-23

Hdu 1897 SnowWolf’s Wine Shop[解题报告] C++

SnowWolf’s Wine Shop

问题描述 :

After retired from hustacm, Sempr(Liangjing Wang) find a part-time-job in Snowwolf(Wei Xu)’s wine shop. There are different qualities of wine in the shop, and all of which has a rating describing the qualities. All the ratings are larger than 0 and smaller than 1,000,000. Everyday nearly Q people will go to his shop and buy a bottle of wine because of his kindness. Once a customer want an X qualified rating but there are no such one, Sempr will sell him a better one with the smallest rating. But the boss of the shop is Snowwolf, you know, so if no wine has no more than Y qualified ratings better than the customer’s request, Sempr will say sorry to them. Every morning, Xiangsanzi will send N bottles of different or same qualified wine.

输入:

In the first line there is an Integer T(0<T<10), which means the number of test cases in the test file, then followed by T test cases.
For each test case;
In the first line, there are 3 Integers, N,Q and Y.
In the second line, there are N integers, which means the quality rating of each bottle of wines.
In the third line, there are Q integers, which means the requests of customers from dawn to dark.
Here, all the Integers are between 0 and 1,000,000

输出:

For each test case, output "Case I:", where I is the case number, then followed by Q different lines of integers, means the quality of wine Sempr will sell that time. If he could not sell any wine, just output -1.

样例输入:

2
2 3 3
2 3
1 2 3
2 3 0
2 3
3 1 2

样例输出:

Case 1:
2
3
-1
Case 2:
3
-1
2


本题是一个简单的模拟题。
对于一些algorithm中的算法,如果在容器本身就有的话,最好先用本身的方法。如本题中的lower_bound();如果用lgorithm中就会TLE。

#include<iostream>
#include<set>
#include<algorithm>
#include<stdio.h>
using namespace std;
int main()
{
	multiset<int> s;
	int m;
	scanf("%d",&m);
	for(int ca=1;ca<=m;++ca)
	{
		s.clear();
		int n,q,y,po;
		scanf("%d%d%d",&n,&q,&y);
		while(n--)
		{
			scanf("%d",&po);
			s.insert(po);
		}
		int v;
		multiset<int>::iterator msp;
		printf("Case %d:\n",ca);
		while(q--)
		{
			scanf("%d",&v);
			msp=s.lower_bound(v);
			if(msp!=s.end()&&*msp-v<=y)
			{
				printf("%d\n",*msp);
				s.erase(msp);
			}
			else
				printf("-1\n");
		}
	}

}

 


  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  3. /*
    * =====================================================================================
    *
    * Filename: 1366.cc
    *
    * Description:
    *
    * Version: 1.0
    * Created: 2014年01月06日 14时52分14秒
    * Revision: none
    * Compiler: gcc
    *
    * Author: Wenxian Ni (Hello World~), [email protected]
    * Organization: AMS/ICT
    *
    * =====================================================================================
    */

    #include
    #include

    using namespace std;

    int main()
    {
    stack st;
    int n,i,j;
    int test;
    int a[100001];
    int b[100001];
    while(cin>>n)
    {
    for(i=1;i>a[i];
    for(i=1;i>b[i];
    //st.clear();
    while(!st.empty())
    st.pop();
    i = 1;
    j = 1;

    while(in)
    break;
    }
    while(!st.empty()&&st.top()==b[j])
    {
    st.pop();
    j++;
    }
    }
    if(st.empty())
    cout<<"YES"<<endl;
    else
    cout<<"NO"<<endl;
    }
    return 0;
    }

  4. 题目需要求解的是最小值,而且没有考虑可能存在环,比如
    0 0 0 0 0
    1 1 1 1 0
    1 0 0 0 0
    1 0 1 0 1
    1 0 0 0 0
    会陷入死循环