Hdu 4546 组合+第k小(二分或优先队列)(西山居初赛)

灰太狼 2022-02-15 01:51 175阅读 0赞

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4546

西山居初赛第一场的题。

思路：最初想法是二分难度，超时……剪枝一下，A掉了。到网上搜解题报告貌似主流算法是优先队列的样子……

二分：

#include <iostream>
    #include <cstdio>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    const int N=100005;
    
    int n,data[N],m;
    vector<int> V[2];
    
    bool Judge (int target)
    {
    	int i,cnt=0;
    	int pre=0,cur=1;
    
    	V[pre].clear();
    	if (data[1]<=target)
    		V[pre].push_back(data[1]),cnt++;
    	int k=2;
    	while (k<=n && cnt<m)
    	{
    		V[cur].clear();
    		sort(V[pre].begin(),V[pre].end());
    
    		int add=data[k++];
    		int len=V[pre].size();
    		bool flag=false;
    
    		for (i=0;i<len && V[pre][i]+add<=target;i++)
    		{
    			int t=V[pre][i];
    			V[cur].push_back(t+add);
    			cnt++;
    			flag=true;
    			V[cur].push_back(t);
    		}
    		if (add<=target)
    		{
    			V[cur].push_back(add);
    			cnt++;
    			flag=true;
    		}
    		if (flag==false)
    			break;
    		swap(pre,cur);
    	}
    	return cnt>=m;
    }
    
    int main ()
    {
    	int T;
    	scanf("%d",&T);
    	for (int Cas=1;Cas<=T;Cas++)
    	{
    		scanf("%d%d",&n,&m);
    		for (int i=1;i<=n;i++)
    			scanf("%d",&data[i]);
    		sort(data+1,data+n+1);
    		int low=0,high=n*1000+5,mid,ans;
    		while (low<=high)
    		{
    			mid=(low+high)>>1;
    			if (Judge(mid))
    				ans=mid,high=mid-1;
    			else
    				low=mid+1;
    		}
    		printf("Case #%d: %d\n",Cas,ans);
    	}
    	return 0;
    }

优先队列：

该思路参考自：http://www.cnblogs.com/CSGrandeur/archive/2013/05/17/3084741.html

c++会WA，G++可以AC……

#include <cstdio>
    #include <iostream>
    #include <cstring>
    #include <algorithm>
    #include <queue>
    using namespace std;
    
    int n,m;
    const int maxn=10010;
    
    struct Node
    {
    	int sum,nex,ith;
    	Node (int sum_, int nex_, int ith_)
    	{
    		sum=sum_;  //当前和
    		nex=nex_;  //加入下个元素的和
    		ith=ith_;  //将要考虑的下个元素
    	}
    	bool operator < (const Node &b) const
    	{
    		return b.nex<nex;
    	}
    };
    
    int data[maxn];
    
    int Cal (int m)
    {
    	priority_queue<Node> q;
    	Node cur(0,data[0],0);
    	q.push(cur);
    	int cnt=0;
    	while (cnt<m)
    	{
    		cur=q.top();
    		q.pop();
    		if (cur.ith >= n)
    			continue;
    		q.push (Node(cur.sum,cur.sum+data[cur.ith+1],cur.ith+1));
    		q.push (Node(cur.nex,cur.nex+data[cur.ith+1],cur.ith+1));
    		cnt++;
    	}
    	for (int i=0;!q.empty();i++)
    		data[i]=q.top().sum,q.pop();
    	sort(data,data+m);
    	return data[m-1];
    }
    
    int main ()
    {
    	int T;
    	scanf("%d",&T);
    	for (int Cas=1;Cas<=T;Cas++)
    	{
    		scanf("%d%d",&n,&m);
    		for (int i=0;i<n;i++)
    			scanf("%d",&data[i]);
    		sort(data,data+n);
    		printf("Case #%d: %d\n",Cas,Cal(m));
    	}
    	return 0;
    }