1、题目：
2、代码（测试点有三个TLE）
/*采用闭散列的方法*/
#include<stdio.h>
#include<malloc.h>
#include<algorithm>
using namespace std;
typedef struct hashtable *HashTable;
typedef struct hashtable
{
int size;
int *ht;
int *state;
} Hashtable;
struct Ti
{
int value;
int t;
} T[1000001];
//判断这个时间段位置是否已经被占，若被占，则往前寻找可以放的时间段，
//之后寻找的时间段只要超过原始时间就不可以了，因为此时炸弹已经飞出射击范围
int Unoccupied(int x,int y,HashTable H)
{
int i,k;
for(i=H->size-1; i>=0; i--)
{
k=(y+i)%H->size;
if(k>=y)
{
return k;
break;
}
if((k<y)&&H->state[k]==1)
{
return k;
break;
}
}
return H->size;
}
//找到合适位置之后就将分数值放在该时间
void HtInsert(int x,int y,HashTable H)
{
int i;
i=Unoccupied(x,y,H);
if(i<y)//插入位置时间一定不能比原始时间大
{
if(i<H->size)
{
H->state[i]=0;
H->ht[i]=x;
}
}
}
//按照分数值降序排序
bool cmp(Ti t1,Ti t2)
{
return t1.value>t2.value;
}
int main()
{
int n;
scanf("%d",&n);
int i,max=0;
for(i=0; i<n; i++)
{
scanf("%d%d",&T[i].t,&T[i].value);
if(max<T[i].t)
{
max=T[i].t;
}
}
HashTable H=(HashTable)malloc(sizeof*H);
H->size=max;
H->ht=(int*)malloc(H->size*sizeof(int));
H->state=(int*)malloc(H->size*sizeof(int));
for(i=0; i<H->size; i++)
{
H->state[i]=1;//1表示该位置还没有被占
H->ht[i]=0;
}
sort(T,T+n,cmp);
for(i=0; i<n; i++)
{
//将分数从大到小放入位置
HtInsert(T[i].value,T[i].t,H);
}
int ans=0;
for(i=0; i<max; i++)
{
ans+=H->ht[i];
}
printf("%d\n",ans);
return 0;
}
3、代码（AC）
/*优先队列*/
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
priority_queue<int> q;
const int N=1000005;
struct Node
{
int t,v;
} a[N];
bool cmp(Node a,Node b)
{
if(a.t==b.t) return a.v<b.v;
return a.t<b.t;
}
int main()
{
int n,i,j,x,ans,sz;
scanf("%d",&n);
sz=q.size();
while(sz--) q.pop();
for(i=1; i<=n; ++i) scanf("%d%d",&a[i].t,&a[i].v);
sort(a+1,a+n+1,cmp);
ans=0;
for(i=a[n].t,j=n; i>=1; --i)
{
//对于每一个时间，将能在这个时间打的push进这个时间点的队列中，队首第一个就是这个时间点该打的
while(j>=1&&a[j].t>=i)
{
q.push(a[j--].v);
}
if(q.empty()) continue;
x=q.top();
q.pop();
ans+=x;
}
printf("%d\n",ans);
return 0;
}