HDU 5596(更新,两种方法)

更新:

这是中文题目的链接:

http://bestcoder.hdu.edu.cn/contests/contest_chineseproblem.php?cid=659&pid=1001

这道题还可以用优先队列来做,优先队列的特性可以很好的返回两个队列中b最小的值。

下面说过了,c[i] += c[i-1]是来获得前缀和。前面的节点没发功增加一次,就相当于b[i]-1,b[i]-c[i-1]的值,就是到达第i时间是,b[i]相对的减少量。我们设置两个队列,根据需要,将b[i]-c[i-1]的值分别放入不同的队列中,例如,当取到0组的数时,将该b[i]-c[i-1]放入0组队列,同时和1组队列的最小值比较,若1组较小,则去掉该元素,直到存在大的为止。

 #include<stdio.h>
#include<queue>
#include<string.h>
#define maxn 50005
using namespace std;
struct node1{
int num;
friend bool operator<(node1 a,node1 b){
return b.num < a.num;
}
};
struct node2{
int group;
int b;
};
node2 a[maxn];
int c[maxn];
int main(){
int t;
scanf("%d",&t);
while(t--){
int n,m;
memset(c,,sizeof(c));
priority_queue<node1>q[];
scanf("%d%d",&n,&m);
for(int i = ;i<=n;i++){
scanf("%d%d",&a[i].group,&a[i].b);
}
for(int i = ;i<m;i++){
int time;
scanf("%d",&time);
c[time]++;
}
int ans = n;
node1 cur;
for(int i = ;i<=n;i++){
c[i] += c[i-];
if(a[i].group){
cur.num = a[i].b-c[i-];
q[].push(cur);
while(!q[].empty()&&q[].top().num<cur.num){
q[].pop();
ans--;
}
}else{
cur.num = a[i].b-c[i-];
q[].push(cur);
while(!q[].empty()&&q[].top().num<cur.num){
q[].pop();
ans--;
}
}
}
printf("%d\n",ans);
}
return ;
}

——————————————————我是分割线————————————————————————————————

题目:

http://acm.hdu.edu.cn/showproblem.php?pid=5596

这道题可以很巧妙的用O(n)的时间复杂度做出来的。首先,当我们用一个数组c存储gt发功的时间时,以该时间为下标之前的b值都会加1,所以可以用c[i] += c[i-1],以获得当前节点之前,已累计法功多少次了,然后c[y]-c[x](y>x)就是以x为下标的gt,到y时间时,通过发功增加的量。

至于为什么要倒着处理呢,因为我们是要去掉小的元素,这样,我们只要从后往前,保存最大的元素,只要存在小于最大元素的,该元素就可以去掉了。

还有,max0、max1分别是1组的最大值和0组的最大值,以gt[i].b-c[i-1]-max0这个式子为例,我们这里假设x<y,max0 = gt[y].b-c[y-1],所以前面那个式子就可以化成gt[x].b-c[x-1]-gt[y].b-c[y-1] = gt[x].b-gt[y].b+c[y-1]-c[x-1],由我们前面的推导,c[y-1]-c[x-1]就是gt[x].b增加的量,这个值加上gt[x].b,如果减去gt[y].b小于0的话,说明该gt是要去掉的,同时要更新max1的值,以为此时处理的是0组的情况,保存最大的。

 #include<stdio.h>
#include<string.h>
#include<algorithm>
#define maxn 50005
#define inf 0x3f3f3f3f
using namespace std;
struct node{
int group;
int b;
};
node gt[maxn];
int c[maxn];
int main(){
int t;
scanf("%d",&t);
while(t--){
int n,m;
memset(c,,sizeof(c));
scanf("%d%d",&n,&m);
for(int i = ;i<=n;i++){
scanf("%d%d",&gt[i].group,&gt[i].b);
}
for(int i = ;i<=m;i++){
int temp;
scanf("%d",&temp);
c[temp]++;
}
for(int i = ;i<=n;i++){
c[i] += c[i-];
}
int ans = n;
int max0 = -inf,max1 = -inf;
for(int i = n;i>;i--){
if(gt[i].group){
if(gt[i].b-c[i-]-max0<)
ans--;
max1 = max(max1,gt[i].b-c[i-]);
}else{
if(gt[i].b-c[i-]-max1<)
ans--;
max0 = max(max0,gt[i].b-c[i-]);
}
}
printf("%d\n",ans);
}
return ;
}

---恢复内容结束---

题目:

http://acm.hdu.edu.cn/showproblem.php?pid=5596

这道题可以很巧妙的用O(n)的时间复杂度做出来的。首先,当我们用一个数组c存储gt发功的时间时,以该时间为下标之前的b值都会加1,所以可以用c[i] += c[i-1],以获得当前节点之前,已累计法功多少次了,然后c[y]-c[x](y>x)就是以x为下标的gt,到y时间时,通过发功增加的量。

至于为什么要倒着处理呢,因为我们是要去掉小的元素,这样,我们只要从后往前,保存最大的元素,只要存在小于最大元素的,该元素就可以去掉了。

还有,max0、max1分别是1组的最大值和0组的最大值,以gt[i].b-c[i-1]-max0这个式子为例,我们这里假设x<y,max0 = gt[y].b-c[y-1],所以前面那个式子就可以化成gt[x].b-c[x-1]-gt[y].b-c[y-1] = gt[x].b-gt[y].b+c[y-1]-c[x-1],由我们前面的推导,c[y-1]-c[x-1]就是gt[x].b增加的量,这个值加上gt[x].b,如果减去gt[y].b小于0的话,说明该gt是要去掉的,同时要更新max1的值,以为此时处理的是0组的情况,保存最大的。

 #include<stdio.h>
#include<string.h>
#include<algorithm>
#define maxn 50005
#define inf 0x3f3f3f3f
using namespace std;
struct node{
int group;
int b;
};
node gt[maxn];
int c[maxn];
int main(){
int t;
scanf("%d",&t);
while(t--){
int n,m;
memset(c,,sizeof(c));
scanf("%d%d",&n,&m);
for(int i = ;i<=n;i++){
scanf("%d%d",&gt[i].group,&gt[i].b);
}
for(int i = ;i<=m;i++){
int temp;
scanf("%d",&temp);
c[temp]++;
}
for(int i = ;i<=n;i++){
c[i] += c[i-];
}
int ans = n;
int max0 = -inf,max1 = -inf;
for(int i = n;i>;i--){
if(gt[i].group){
if(gt[i].b-c[i-]-max0<)
ans--;
max1 = max(max1,gt[i].b-c[i-]);
}else{
if(gt[i].b-c[i-]-max1<)
ans--;
max0 = max(max0,gt[i].b-c[i-]);
}
}
printf("%d\n",ans);
}
return ;
}
上一篇:JS用斜率判断鼠标进入DIV四个方向的方法 判断鼠标移入方向


下一篇:mongo语法和mysql语法对比学习