URAL 1998 The old Padawan - c++编程基础

题目只给了500ms，注意超时问题，一开始的几发都超时了，后来想到了预处理，从后往前推即可，为了防止t的大小可能有问题，所以进行了排序，还有人用二分做的，比较犀利先贴一个我的思路

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
           #include
           
             #include
            
              #include
             
               #include
              
                #define ll long long #define eps 1e-7 #define inf 0xfffffff const ll INF = 1ll<<61; using namespace std; //vector
               
                 > G; //typedef pair
                
                  P; //vector
                 
                   > ::iterator iter; // //map
                  
                   mp; //map
                   
                    ::iterator p; // int n,m,k; int w[100000 + 5]; int t[100000 + 5]; int sum[100000 * 2];//当前往前面第一次超过k的石头和 int step[100000 * 2];//当前往前需要回头几步 void clear() { memset(w,0,sizeof(w)); memset(t,0,sizeof(t)); memset(sum,0,sizeof(sum)); memset(step,0,sizeof(step)); } void init() { sum[n] = w[n]; int tempn = n - 1; int cnt = 1; while(sum[n] <= k && tempn >=1) {//最后一个要单独拎出来 cnt++; sum[n] += w[tempn--]; } step[n] = cnt; int tmpn = n - 1; while(tmpn) { sum[tmpn] = sum[tmpn + 1] - w[tmpn + 1]; cnt--; while(sum[tmpn] <=k &&tempn >= 1) { cnt++; sum[tmpn] += w[tempn--]; } step[tmpn] = cnt; if(tempn <= 0) { for(int i=tmpn;i>0;i--)//前面和已经无法超过k，所以退到直至第一次为止 step[i] = i; break; } tmpn--; } } int main() { while(scanf("%d %d %d",&n,&m,&k) == 3) { clear(); for(int i=1;i<=n;i++) scanf("%d",&w[i]); for(int i=1;i<=m;i++) scanf("%d",&t[i]); sort(t + 1,t + m + 1); init(); int ans = 0; int mark = 0; for(int i=1;i<=m;i++) { int cha = (t[i] - t[i-1]); mark += cha; if(mark > n) { mark -= cha; break; } ans += cha; mark = mark - 1 - step[mark - 1]; } ans += n - mark; printf("%d\n",ans); } return EXIT_SUCCESS; } /* 5 2 4 1 2 3 4 5 4 5 5 2 4 3 2 3 4 5 3 4 */

接下来是二分做的，

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         using namespace std; #define N 100010 int a[N],t[N],sum[N],n,m,k,ans; int find(int x) { int l=0,r=n,res=0; while(l<=r) { int mid=(l+r)/2; if(sum[mid]