4 条题解

  • 6
    @ 2022-7-1 17:45:38

    再反复看 活动选择比赛数 后,我确定了这两题就是题目说法变了,但做法不变。

    因此,直接把 活动选择 的代码复制过来即可。

    活动选择 AC 代码( 74ms ):

    #include <cstdio> //printf
    using namespace std;
    
    int n , ans;
    int t = -1; //上一个比赛的结束时间 
    
    struct QWQ{
        int bt , et;
        //起始时间,结束时间 
    }qwq[100005];
    
    void qsort(int l , int r){ //用二分优化的冒泡排序(快排) 
        int mid = qwq[(l + r) >> 1].et;
        // x >>= 1 位运算 等同于  x /= 2
        int i = l , j = r;
        do{
            while(qwq[i].et < mid) i++;
            while(qwq[j].et > mid) j--;
            if(i <= j){
            	QWQ t = qwq[i];
            	qwq[i] = qwq[j];
            	qwq[j] = t;
                i++;
                j--;
            }
        }while(i <= j);
        if(l < j) qsort(l , j); //递归 
        if(i < r) qsort(i , r); 
    }
    
    int main(void){
    	scanf("%d" , &n);
    	for(register int i = 0;i < n;i++)  //循环加速 
    		scanf("%d%d" , &qwq[i].bt , &qwq[i].et);
    	qsort(0 , n - 1); //快排 
    	for(register int i = 0;i < n;i++){
    		if(qwq[i].bt >= t){
    			ans++;
    			t = qwq[i].et;
    		}
    	}
    	printf("%d" , ans);
    }
    
    
    • 4
      @ 2023-2-12 9:37:50
      #include <bits/stdc++.h>
      using namespace std;
      struct hd{int begini, endi;};
      hd a[1000001];
      bool cmp(hd a,hd b){
          return a.endi<b.endi;
      }
      int n;
      int main(){   
          cin>>n;
          for(int i=1;i<=n;i++){
              cin>>a[i].begini>>a[i].endi;
          }sort(a+1,a+n+1,cmp);
          int ans=1,cur=a[1].endi;
          for(int i=2;i<=n;i++){
              if(a[i].begini<cur)
                  continue;
              ans++;
              cur=a[i].endi;
          }cout<<ans;
          return 0;
      }//这不就跟活动选择一样吗()
      //这个代码在活动选择和比赛数通用
      
      
      
      </span>
      • -2
        @ 2022-8-23 15:14:26
        struct hh
        {
            int l,r;
        }a[1000005];
        bool cmp(hh x1,hh x2)
        {
            return x1.r<x2.r;
        }
        sort(a+1,a+n+1,cmp);
        int t=a[1].r;
        for (int i=2;i<=n;i++)
        {
            if (a[i].l>=t)
            {
                t=a[i].r;
                ans++;
            }
        }
        
        • -2
          @ 2022-4-24 16:14:10

          鼓励大家写题解,但注意题解格式。

          给代码两端加上这个会舒服一些

          ```cpp

          你的代码

          ```

          </span>

          这个点在键盘的左上角tab上面那个键,注意切换输入法

          #include<iostream>
          using namespace std;
          int main()
          {
              int n;
              cin>>n;//这是一个注释
              return 0;
          } 
          

          请注意严禁抄袭题解,写题解不要只放代码,需加上你的思路或代码注释。

          抄袭题解一经发现直接取消成绩。

          • 1

          信息

          ID
          1331
          时间
          1000ms
          内存
          256MiB
          难度
          5
          标签
          递交数
          447
          已通过
          158
          上传者