| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
帮忙看一下 为什么wa呀 楼下的数据都过了呀!!!#include<iostream>
#include<vector>
#include <algorithm>
#include<queue>
using namespace std;
struct node
{
int p,d;
node(){p=0;d=0;}
};
class Supermarket
{
public:
void input(int);
void solve();
private:
priority_queue<int>schedule[10001];
vector<int> num;
vector<int> deadline;
int N,m;
};
void Supermarket::input(int n)
{
int i,j=1,px,dx;
node tt;
N=n;
num.assign(n+1,0);
deadline.assign(n+1,0);
for(i=1;i<=n;i++)
{
scanf("%d%d",&px,&dx);
tt.d=dx;
tt.p=px;
if(schedule[dx].empty())
deadline[j++]=dx;
schedule[dx].push(tt.p);
}
m=j;
sort(deadline.begin(),deadline.begin()+j);
}
void Supermarket::solve()
{
int i,l=1,j=1,t,k,sum;
i=deadline[l];
for(j=1;j<=N;j++)
{
k=j;
sum=0;
while(!schedule[i].empty())
{
t=deadline[k];
if(t==0)
{
while(!schedule[i].empty())
{
schedule[i].pop();
}
break;
}
while(t>deadline[k-1]&&!schedule[i].empty())
{
sum+=schedule[i].top();
schedule[i].pop();
t--;
}
if(num[k-1]+sum>num[j])
{
num[j]=num[k-1]+sum;
}
k--;
}
i=deadline[++l];
}
//printf("\n");
printf("%d\n",num[m-1]);
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
Supermarket bb;
bb.input(n);
bb.solve();
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator