注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ1293][SCOI2009]生日礼物  

2014-10-19 23:43:42|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1293: [SCOI2009]生日礼物

想了1h+结果最后发现是水题QAQ
题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
int scan(){
char cc=' ';int re=0,fh=1;
while(cc==' '||cc=='\r'||cc=='\n')cc=getchar();
if(cc=='+')cc=getchar(),fh=1;
if(cc=='-')cc=getchar(),fh=-1;
while('0'<=cc&&cc<='9'){
re=re*10+cc-'0';
cc=getchar();
}return re*fh;
}
const int N = 1E6+10;
const int M = 65;
typedef long long LL;
int n,m,mm;
//int data[N],st[M],en[M];
int num[60];
struct Data{
int i,c;
Data(){}
Data(int ii,int color):i(ii),c(color){}
}data[N];
bool operator < (Data a,Data b){return a.i < b.i;}
void add(int a,short t){
if(t > 0){
if(!num[a])num[0]--;
num[a]++;
}else{
num[a]--;
if(!num[a])num[0]++;
}
}
int main(){
//freopen("gift.in","r",stdin);
//freopen("gift.out","w",stdout);
int i,j,a,b;
n = scan();m = scan();
for(i=1;i<=m;i++){
a = scan();
for(j=1;j<=a;j++){
b = scan();
data[++mm] = Data(b,i);
}
}
//sort(list+1,list+1+n);
data[0] = Data(-1,0);
sort(data+1,data+1+n);
int r = 0;num[0] = m;
int ans = -1;
for(i=1;i<=n;i++){
while(num[0] && r<n)add(data[++r].c,+1);
while(data[r+1].i == data[r].i && r<n)add(data[++r].c,+1);
if(num[0])break;
if(ans < 0)ans = data[r].i - data[i].i;
else ans = min(ans,data[r].i - data[i].i);
for(j=i;j<=n;j++)
if(data[j].i == data[i].i) add(data[j].c,-1);
else break;
i = j-1;
}
printf("%d\n",(int)ans);
return 0;
}

题解:
双向队列乱搞。。。
不难看出最优解一定是以珠子为左右端点的连续区间。
排一遍序,然后枚举每个点作为左端点,向右扩展右端点直到这个区间里包括了所有的珠子。
官方题解说标解应该是NlogK的堆乱搞,NlogN做法只有80分。
个人觉得sort一遍虽然时间复杂度高一些,但是常数较堆更小。
我找到官方的两个程序比较了一下,最大的点NlogN 0.7+s NlogK 0.5+s,我的程序NlogN 0.5+s,和标解几乎一样,所以在考场上如果真的写了估计也卡不掉- -|
---------------------------------------------------------------------------------------------------------------------------------------
一开始第一反应是二分答案,然后第二反应是T出翔……
写了一下结果真的只过了50%的点QAQ
  评论这张
 
阅读(42)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017