首页 > 代码库 > BestCoder Round #3HDU 4907

BestCoder Round #3HDU 4907

2024-07-15 17:11:49   222人阅读

1. HDU 4907：http://acm.hdu.edu.cn/showproblem.php?pid=4907

  中文题我就不说题意了，直接说解题思路吧！

  ① 第一种思路就是我比赛时的思路，将a数组先全部清为零，当输入机器在ti时间执行第i个任务时，将a[ti]置为1，开始输入q（表示在q时间有一个工作表之外的任务请求）写一个循环，让a数组从a[q]开始循环，直到找到a[J]为0，输出j。这种方法时间超限了，但是在输入q之前先预处理，打一个表就不会超时了。

  附上代码：

    

 1 #include<stdio.h> 2 #include<string.h> 3 int t[200010],s[200010]; 4 int main() 5 { 6     int T,m,n,i,j,k,a; 7     scanf("%d",&T); 8     while(T--) 9     {10         scanf("%d%d",&m,&n);11         memset(t,0,sizeof(t));12         for(i=1; i<=m; i++)13         {14             scanf("%d",&a);15             t[a]=1;16         }17         memset(s,0,sizeof(s));18         k=1;19         for(i=1; i<=200000; i++)20             if(t[i]==0)21             {22                 for(j=k; j<=i; j++)23                     s[j]=i;24                 k=i+1;25             }26         while(n--)27         {28             scanf("%d",&a);29             printf("%d\n",s[a]);30         }31     }32     return 0;33 }

   ②第二种思路是二分法，输入a[],后排下序，然后记录每个数字出现的位置，对于询问q,如果q不存在直接输出q，

如果q存在，假设q所在的位置为pos，那么二分【pos,n】,二分判断的依据是如果mid-p==a[mid]-a[p],那么left=mid+1,否则right=mid-1.

附上代码：

    

 1 #include<iostream> 2 #include<algorithm> 3 #include<stdio.h> 4 #include<string.h> 5 using namespace std; 6 #define maxn 100010 7 int a[maxn]; 8 int main() 9 {10     int T,i;11     scanf("%d",&T);12     while(T--)13     {14         int n,m;15         scanf("%d%d",&n,&m);16         for(i=0; i<n; i++)17             scanf("%d",&a[i]);18         sort(a,a+n);19         while(m--)20         {21             int q;22             scanf("%d",&q);23             int pos=int(lower_bound(a,a+n,q)-a);24             if(pos==n||a[pos]!=q)25                 printf("%d\n",q);26             else27             {28                 int left=pos+1,right=n;29                 while(left<right)30                 {31                     int mid=(left+right)>>1;32                     if(a[mid]-q==mid-pos)33                         left=mid+1;34                     else35                         right=mid;36                 }37                  printf("%d\n",a[left-1]+1);38             }39         }40     }41     return 0;42 }

后记：

    函数lower_bound()在first和last中的前闭后开区间进行二分查找，返回大于或等于val的第一个元素位置。如果所有元素都小于val，则返回last的位置。

  


联系
我们