处理 true sca nss height print cst i++ 复杂
Input第1行:2个数N, M中间用空格分隔,N为井的深度,M为盘子的数量(1 <= N, M <= 50000)。
第2 - N + 1行,每行1个数,对应井的宽度Wi(1 <= Wi <= 10^9)。
第N + 2 - N + M + 1行,每行1个数,对应盘子的宽度Di(1 <= Di <= 10^9)Output输出最终落到井内的盘子数量。Sample Input
- 7 5
- 5
- 6
- 4
- 3
- 6
- 2
- 3
- 2
- 3
- 5
- 2
- 4
Sample Output
- 4
刚开始想的是用两个队列来维护,但是.......后来用两个数组来存放盘子和井的宽度由于用到了两重循环结果TLE了
- #include<bits/stdc++.h>
- #define maxn 50010
- using namespace std;
- int main()
- {
- int n,m;
- int i,j;
- int flag;
- int logo;
- int a[maxn],b[maxn];
- scanf("%d%d",&n,&m);
- a[0] = 0;
- for(i=1; i<=n; i++)
- {
- scanf("%d",&a[i]);
- }
- for(i=0; i<m; i++)
- {
- scanf("%d",&b[i]);
- }
- flag = n;
- for(j=0; j<m; j++)
- {
- logo = 1;
- for(i=0; i<flag; i++)
- {
- if(b[j] > a[i])
- {
- flag = i;
- logo = 0;
- }
- }
- if(logo == 1)
- flag--;
- if(flag == 0)
- {
- printf("%d\n",j);
- break;
- }
- }
- return 0;
- }
然后看了大神的博客发现时间复杂度可以简化到O(n),具体的方法就是让井的下层宽度小于或者等于上层宽度,然后从上往下以此比较
- #include<bits/stdc++.h>
- #include<string.h>
- #define maxn 50010
- using namespace std;
- int main()
- {
- int n,m;
- int i,j;
- int flag;
- int a[maxn],b[maxn];
- scanf("%d%d",&n,&m);
- for(i=1; i<=n; i++)
- {
- scanf("%d",&a[i]);
- if(i >= 2)
- a[i] = min(a[i],a[i-1]);
- }
- flag = 0;
- for(j=0; j<m; j++)
- {
- scanf("%d",&b[j]);
- while(a[n] < b[j])
- n--;
- if(n > 0)
- {
- flag++;
- n--;
- }
- }
- printf("%d\n",flag);
- return 0;
- }
也有人用栈来解题
- #include<iostream>
- #include<cstring>
- #include<math.h>
- #include<stdlib.h>
- #include<cstring>
- #include<cstdio>
- #include<utility>
- #include<algorithm>
- #include<map>
- #include<stack>
- using namespace std;
- typedef long long ll;
- const int Max = 1e5+5;
- const int mod = 1e9+7;
- const int Hash = 10000;
- const int INF = 1<<30;
- const ll llINF = 1e18;
- int n, m;
- int well[Max], plate[Max];
- int main( )
- {
- //freopen("input.txt", "r", stdin);
- while(cin>>n>>m)
- {
- int ans = 0, Min = INF;
- for(int i=0; i<n; i++)
- scanf("%d", well+i);
- for(int i=0; i<m; i++)
- scanf("%d", plate+i);
- //预处理,用单调栈来处理数据
- stack<int> st;
- for(int i=0; i<n; i++)
- {
- if(well[i]<Min)
- Min = well[i];
- st.push(Min);
- }
- int k = 0;
- while(!st.empty() && k<m)//井满或者盘子用尽都结束
- {
- if(st.top()<plate[k])//盘子大继续出栈
- {
- st.pop( );
- continue;
- }
- ans++;//在这个位置卡住一个盘子
- st.pop( );
- k++;
- }
- cout<<ans<<endl;
- }
- return 0;
- }
扔盘子(思维)
来源: http://www.bubuko.com/infodetail-2333490.html