折腾了好久，才知道原来是题意理解错了，原来每天都可以完成m个工作，在截至日期完成就行了，用了刚写的堆类，应该没什么问题
1
#include <stdio.h>
2
#include <vector>
3
#include <algorithm>
4
#define maxn 100005
5
using namespace std;
6
class my_heap//最小堆
7
{
8
public:
9
int h[maxn];
10
int size;
11
my_heap()
12
{
13
size=0;
14
}
15
void siftdown(int start,int end)//下移
16
{
17
int i=start,j=2*i+1,buf=h[i];
18
while(j<=end)
19
{
20
if(j<end&&h[j]>h[j+1]) j++;
21
if(h[j]>=buf) break;
22
else
23
{
24
h[i]=h[j];
25
i=j;
26
j=2*j+1;
27
}
28
h[i]=buf;
29
}
30
}
31
void siftup(int pos)//上移
32
{
33
int i=pos,j=(i-1)/2,temp=h[i];
34
while(i>0)
35
{
36
if(h[j]<=temp) break;
37
else
38
{
39
h[i]=h[j];
40
i=j;
41
j=(j-1)>>1;
42
}
43
h[i]=temp;
44
}
45
}
46
void insert(int elem)//插入
47
{
48
h[size]=elem;
49
siftup(size);
50
size++;
51
}
52
void remove_min()//删除最小值
53
{
54
if(size<=1)
55
{
56
size--;
57
return ;
58
}
59
swap(h[0],h[size-1]);
60
size--;
61
siftdown(0,size-1);
62
}
63
void intial()//建立堆
64
{
65
int pos=(size-2)>>1;
66
while(pos>=0)
67
{
68
siftdown(pos,size-1);
69
pos--;
70
}
71
}
72
void swap(int &a,int &b)
73
{
74
int temp=a;
75
a=b;
76
b=temp;
77
}
78
void heap_sort()//堆的初始化
79
{
80
int len=size;
81
intial();
82
while(len>1)
83
{
84
swap(h[0],h[len-1]);
85
len--;
86
siftdown(0,len-1);
87
}
88
printf("sorted heap\n");
89
for(int i=0;i<size;i++)
90
{
91
printf("%d ",h[i]);
92
}
93
}
94
void input()
95
{
96
printf("input the size\n");
97
scanf("%d",&size);
98
printf("input the number\n");
99
for(int i=0;i<size;i++)
100
{
101
scanf("%d",&h[i]);
102
}
103
}
104
};
105
class node
106
{
107
public:
108
int p;
109
int t;
110
node(int _p,int _t):p(_p),t(_t)
{}
111
};
112
class cmp
113
{
114
public:
115
bool operator () (const node &a,const node &b) const
116
{
117
return (a.t<b.t);
118
}
119
};
120
vector<node> l;
121
my_heap he;
122
int n,m;
123
int main()
124
{
125
while(scanf("%d %d",&n,&m)!=EOF)
126
{
127
l.clear();
128
he.size=0;
129
int p,t;
130
for(int i=0;i<n;i++)
131
{
132
scanf("%d %d",&p,&t);
133
l.push_back(node(p,t));
134
}
135
sort(l.begin(),l.end(),cmp());
136
int sum=0;
137
p=-1;
138
t=0;
139
for(int i=0;i<n;i++)
140
{
141
t+=(l[i].t-p)*m;
142
if(t==0)
143
{
144
if(he.size==0) continue;
145
else
146
{
147
if(l[i].p>he.h[0])
148
{
149
sum+=l[i].p-he.h[0];
150
he.remove_min();
151
he.insert(l[i].p);
152
}
153
}
154
}
155
else
156
{
157
sum+=l[i].p;
158
he.insert(l[i].p);
159
t--;
160
}
161
p=l[i].t;
162
}
163
printf("%d\n",sum);
164
}
165
return 0;
166
}
167
168
posted on 2011-02-13 16:22
avcpp 阅读(147)
评论(0) 编辑 收藏 引用