Editorial for Bán dừa
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của flashmt
#include <iostream> #include <algorithm> #include <cstdio> #define fr(a,b,c) for (a=b;a<=c;a++) #define N 1000100 using namespace std; int re,n,a[N],m,st[N],pos[N]; int main() { int i; cin >> n; fr(i,1,n) scanf("%d",&a[i]); st[0]=-1; m=pos[0]=0; fr(i,1,n) if (a[i]>st[m]) { st[++m]=a[i]; pos[m]=i; } else { while (a[i]<=st[m]) { re=max(re,(st[m]<=i-pos[m]+(a[i]==st[m])?st[m]:0)); m--; } st[++m]=a[i]; } fr(i,1,m) re=max(re,(st[i]<=n-pos[i]+1?st[i]:0)); cout << re << endl; return 0; }
Code mẫu của ladpro98
program kagain; uses math; const fi=''; fo=''; var a:array[0..1000009] of longint; left,right:array[0..1000009] of longint; area,dau,cuoi,n,t,i,j:longint; inp,oup:text; procedure openFile; begin assign(inp,fi); reset(inp); assign(oup,fo); rewrite(oup); end; procedure closeFile; begin close(inp); close(oup); end; procedure process; var i,t:longint; begin area:=0; for i:=1 to n do begin left[i]:=0; right[i]:=0; end; left[1]:=0; for i:=2 to n do begin t:=i-1; while a[t]>=a[i] do t:=left[t]; left[i]:=t; end; right[n]:=n+1; for i:=n-1 downto 1 do begin t:=i+1; while a[t]>=a[i] do t:=right[t]; right[i]:=t; end; for i:=1 to n do begin t:=right[i]-left[i]-1; if t>=a[i] then area:=max(area,a[i]); end; end; begin openFile; readln(inp,n); for j:=1 to n do readln(inp,a[j]); process; write(oup,area); close(oup); end.
Code mẫu của RR
#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <algorithm> #include <vector> #include <set> #include <map> #include <stack> #include <queue> #include <string> #include <deque> #include <complex> #include <sstream> #include <iomanip> #define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++) #define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--) #define REP(i,a) for(int i=0,_a=(a); i<_a; i++) #define ll long long #define F first #define S second #define PB push_back #define MP make_pair using namespace std; const double PI = acos(-1.0); int INP,AM; #define BUFSIZE (1<<10) char BUF[BUFSIZE+1], *inp=BUF; #define GETCHAR(INP) { \ if(!*inp) { \ fread(BUF,1,BUFSIZE,stdin); \ inp=BUF; \ } \ INP=*inp++; \ } #define DIG(a) (((a)>='0')&&((a)<='9')) #define GN(j) { \ AM=0;\ GETCHAR(INP); while(!DIG(INP) && INP!='-') GETCHAR(INP);\ if (INP=='-') {AM=1;GETCHAR(INP);} \ j=INP-'0'; GETCHAR(INP); \ while(DIG(INP)){j=10*j+(INP-'0');GETCHAR(INP);} \ if (AM) j=-j;\ } int n, st[1000111], a[1000111], l[1000111], r[1000111], top; int main() { // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); GN(n); FOR(i,1,n) GN(a[i]); top = 0; st[0] = 0; FOR(i,1,n) { while (top && a[st[top]] >= a[i]) top--; l[i] = st[top] + 1; st[++top] = i; } top = 0; st[0] = n+1; FORD(i,n,1) { while (top && a[st[top]] >= a[i]) top--; r[i] = st[top] - 1; st[++top] = i; } int res = 0, u; FOR(i,1,n) { u = r[i] - l[i] + 1; if (u < a[i]) continue; res = max(res, min(u, a[i])); } cout << res; return 0; }
Code mẫu của hieult
#include <stdio.h> #include <algorithm> //#include <conio.h> #define Max 1111111 using namespace std; int T,n,k,a[Max],left[Max],right[Max],r[Max],l[Max]; int main() { scanf("%d",&n); for(int j=1;j<=n;j++) scanf("%d",&a[j]); int u = 1; r[1] = 1; for(int i = 2;i<=n;i++){ if(a[i]<a[r[u]]){ while(a[i]<a[r[u]] && u>0){ right[r[u]] = i-1; u--; } } r[++u] = i; if(i==n) for(int j = 1;j<=u;j++) right[r[j]] = n; } u = 1; l[1] = n; for(int i = n-1;i>0;i--){ if(a[i]<a[l[u]]){ while(a[i]<a[l[u]] && u>0){ left[l[u]] = i+1; u--; } } l[++u] = i; if(i==1) for(int j = 1;j<=u;j++) left[l[j]] = 1; } //printf("%ld %ld %ld",left[4],left[3],left[2]); int kq = 0; for(int j=1;j<=n;j++) { if(a[j]<=right[j]-left[j]+1) kq = max(kq,min(right[j]-left[j]+1,a[j])); } printf("%d",kq); //getch(); }
Comments