首页 > ACM题库 > HDU-杭电 > HDU 3673-David Shopping[解题报告]HOJ
2014
11-30

HDU 3673-David Shopping[解题报告]HOJ

David Shopping

问题描述 :

David comes to Chengdu for ACM-ICPC 2007. After learning Chengdu is a beautiful city, David decides to buy his friends some gifts.

The capacity of David’s pocket is so small that it can only contain M gifts. Considering the diversity of his gifts, David would not buy two of the same kind. And some typical gift should be chosen to represent the features of Chengdu.

David will walk down from north to south and visit N shops one by one along the shopping street. There is ONLY ONE type of gift sold in each shop.

David has such a poor memory that he can’t remember how many shops sell gift K . So he will write a number L on this gift he bought in his pocket, to indicate how many shops where sell gift K . In David’s opinion, the smaller the number L is, the better the gift (David like uncommon gifts).

When David stops in a shop which sells gift K , the following three situations he might come across.

1. If there is not gift K in his pocket and still some place for it, He will buy without hesitation. Before putting it into the pocket, David will write down the number `1′ on the gift to indicate that he has once seen one shop selling it.
2. If there is gift K in his pocket, David will just replace the number L with L + 1 , indicating L + 1 shops sell gift K .
3. If there is not gift K in his pocket and the pocket is full, David would like to regard no shops selling gift K (because he cannot remember whether or not he has met gift K ), so he will have to discard one gift in his pocket to release a place for the gift K . But which gift should be discarded? According to the follow rule:

He chooses the gift that has the biggest number L on it. If several gifts have the same biggest number L , he will discard the one which has been putted into the pocket at the earliest time. After discarding the gift, he will put gift K into his pocket and write number `1′ on gift K .

Now, your task is to write a program to record the number of these gifts which have been discarded by David.

For example:

David’s pocket has the capacity only for two gifts. There are 5 shops in the street, and each shop sells only one type of gift. The selling sequence of gifts is 1, 2, 1, 3, and 1.

In shop 1, the pocket is empty, so he will buy gift 1, write a number `1′ on this gift, and then put it into his pocket.

When he comes to shop 2, there is one place left in his pocket, so he buys gift 2, write a number `1′ on it, and then put it into the pocket.

When walking into shop 3, he has already got gift 1 in his pocket, so he will replace the number L (here, L = 1 ) with L + 1 .

When David visits shop 4, the pocket is full, but without gift 3 in it, so he has to discard one gift to release a place for gift 3. The number L on gift 1 is `2′, but the number L on gift 2 is `1′, so he will discard gift 1, write number 1 on gift 3 and then put it into the pocket.

In shop 5, the pocket is full, gift 1 is not in it, he should will discard a gift to find place for gift 1. The number L on gift 2 is `1′, the number L on gift 3 is also `1′. They have the same L , but gift 2 put into the pocket earlier than gift 3. So he discards gift 2, write number `1′ on gift 1 and then put it into the pocket. At the end of the street, David gets two gifts in his pocket, number `1′ on gift 3 and number `1′ on gift 1. The number of discarded gifts is 2.

输入:

There are multiple test cases in the input file. Each test case contains two lines.

The first line has two positive integers M and N ( M<=50, 000 and N<=100, 000 ) where M (the capacity of pocket) shows how many gifts it can take and N is the number of shops in the street. The second line has N positive integers Ki (Ki < 2^20, i = 1, 2,…, N) indicating the type of gift sold in the i -th shop. M = 0 and N = 0 indicate the end of file and should not be processed by your program.

输出:

There are multiple test cases in the input file. Each test case contains two lines.

The first line has two positive integers M and N ( M<=50, 000 and N<=100, 000 ) where M (the capacity of pocket) shows how many gifts it can take and N is the number of shops in the street. The second line has N positive integers Ki (Ki < 2^20, i = 1, 2,…, N) indicating the type of gift sold in the i -th shop. M = 0 and N = 0 indicate the end of file and should not be processed by your program.

样例输入:

3 5 
1 2 3 2 4 
2 4 
1 2 2 1 
2 6 
1 2 2 1 1024 1 
2 10 
1 2 3 2 4 2 3 6 7 8 
2 1 
1048575 
6 16 
10 1 2 3 4 5 6 1 2 3 6 5 4 10 1 6 
0 0

样例输出:

Case 1: 1
Case 2: 0
Case 3: 2
Case 4: 7
Case 5: 0
Case 6: 3

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<map>
#include<string.h>
using namespace std;

#define MAXN 100100

map<int,int> mp;

int Max[MAXN<<2],in[MAXN],inT[MAXN],shop[MAXN];

int getmax(int x,int y){
	if (in[x]>in[y]) return x;
	if (in[x]<in[y]) return y;
	if (inT[x]<inT[y]) return x;
	else return y;
}

void update(int x,int l,int r,int rt){
	if (l==r){
		Max[rt]=x;
		return;
	}
	int m=(l+r)>>1;
	if (x<=m) update(x,l,m,rt<<1);
	else update(x,m+1,r,rt<<1|1);
	Max[rt]=getmax(Max[rt<<1],Max[rt<<1|1]);
}

int main(){
	int caseT=0,S,n,x;
	while (scanf("%d%d",&S,&n)!=EOF){
		if (S==0&&n==0) break;
		mp.clear();
		int cnt=0;
		for (int i=1;i<=n;i++){
			scanf("%d",&x);
			if (mp.find(x)==mp.end()) mp[x]=++cnt;
			shop[i]=mp[x];
		}
		memset(Max,0,sizeof(Max));
		memset(in,0,sizeof(in));
		memset(inT,0,sizeof(inT));
		int now=0,ans=0;
		for (int i=1;i<=n;i++){
			if (in[shop[i]]){
				in[shop[i]]++;
//				cout<<1<<' '<<i<<' '<<shop[i]<<endl;
			}
			else if (now<S){
				in[shop[i]]++; inT[shop[i]]=i;
				now++;
	//			cout<<2<<' '<<i<<endl;
			}
			else {
				int t=Max[1];
				in[t]=0; inT[t]=0; in[shop[i]]++; inT[shop[i]]=i;
				update(t,1,n,1);
				ans++;
			}
			update(shop[i],1,n,1);
		//	cout<<Max[1]<<' '<<in[Max[1]]<<' '<<inT[Max[1]]<<endl;
		}
		printf("Case %d: %d\n",++caseT,ans);
	}
	return 0;
}

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

  2. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。

  3. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?

  4. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同,其树的前、中、后序遍历是相同的,但在此处不能使用中序遍历,因为,中序遍历的结果就是排序的结果。经在九度测试,运行时间90ms,比楼主的要快。

  5. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。