首页 > 代码库 > 1279 扔盘子
1279 扔盘子
思路:先将井口处理成递增的序列,然后再二分每个盘子插入的位置。
1 #include <iostream> 2 #include <queue> 3 #include <stack> 4 #include <cstdio> 5 #include <vector> 6 #include <map> 7 #include <set> 8 #include <bitset> 9 #include <algorithm> 10 #include <cmath> 11 #include <cstring> 12 #include <cstdlib> 13 #include <string> 14 #include <sstream> 15 #include <time.h> 16 #define x first 17 #define y second 18 #define pb push_back 19 #define mp make_pair 20 #define lson l,m,rt*2 21 #define rson m+1,r,rt*2+1 22 #define mt(A,B) memset(A,B,sizeof(A)) 23 #define mod 1000000007 24 using namespace std; 25 typedef long long LL; 26 const double PI = acos(-1); 27 const int N=1e5+10; 28 const int inf = 0x3f3f3f3f; 29 const LL INF=0x3f3f3f3f3f3f3f3fLL; 30 int w[N],D[N]; 31 int main() 32 { 33 #ifdef Local 34 freopen("data.txt","r",stdin); 35 #endif 36 int n,m,ans=0; 37 cin>>n>>m; 38 for(int i=0;i<n;i++)cin>>w[i]; 39 for(int i=0;i<m;i++)cin>>D[i]; 40 for(int i=1;i<n;i++) 41 { 42 if(w[i]>w[i-1])w[i]=w[i-1]; 43 } 44 sort(w,w+n); 45 w[n]=inf; 46 for(int i=0,k=0;i<m;i++) 47 { 48 k=lower_bound(w+k,w+n+1,D[i])-w+1; 49 if(k>n)break; 50 ans++; 51 } 52 cout<<ans<<endl; 53 #ifdef Local 54 cerr << "time: " << (LL) clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl; 55 #endif 56 }
1279 扔盘子
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。