HDU5090(贪心+priority_queue优化)

        两种优先队列的声明方法

        std::priority_queue<T> que;

        std::priority_queue<T, std::vector<T>, cmp> que;

        优先队列的top默认是大的，若要小的优先，则要定义一个结构体cmp，将()运算符重载

因为优先队列的优先级通过！cmp来判断，cmp要这样写：

struct cmp
{
	bool operator()(int &a,int &b)
	{
		return a>b;
	}    
};

        题目略

思路:先对a数组升序数据排序，逐一判断a[i]与i的关系)(i从1开始)，

        若==就continue；

        小于就a[i]+k，i--，重新对a进行排序；

        大于就直接tom赢了。

每次小于都sort一次:15ms

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int M,N,K,a[105],n;
int main()
{
scanf("%d",&M);
while(M--)
{
memset(a,0,sizeof(a));
scanf("%d %d",&N,&K);
for(int i=1;i<=N;i++)
{
scanf("%d",&a[i]);			
}
sort(a+1,a+N+1);
int flag = 1;
for(int i=1;i<=N;i++)
{
if(a[i]==i)
continue;
else if(a[i]<i)
{
a[i] += K;
i--;
sort(a+1,a+N+1);
}
else
{
flag = 0;
break;
}
}
if(flag)
printf("Jerry\n");
else
printf("Tom\n");
}
}

用priority_queue优化:0ms

#include<cstdio>
#include<queue>
using namespace std;

struct cmp
{
bool operator()(int &a,int &b)
{
return a>b;
}

};
int M,N,K,a,n;
int main()
{
scanf("%d",&M);
while(M--)
{
priority_queue<int, vector<int>, cmp> que;
scanf("%d %d",&N,&K);
for(int i=1;i<=N;i++)
{
scanf("%d",&a);
que.push(a);
}
int flag = 1;
for(int i=1;i<=N;i++)
{
a = que.top();
que.pop();
if(a==i)
continue;
else if(a<i)
{
a += K;
que.push(a);
i--;
}
else
{
flag = 0;
break;
}
}
if(flag)
printf("Jerry\n");
else
printf("Tom\n");
}
}