Editorial for VOI 11 Bài 4 - Nối điểm đen trắng
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> #define fr(a,b,c) for (a=b;a<=c;a++) using namespace std; struct rec { int x,y; }; int n,re,i; rec a[200002]; bool cmp(rec i,rec j) { return (i.x<j.x); } int main() { cin >> n; fr(i,1,n*2) { scanf("%d",&a[i].x); if (i>n) a[i].y=1; } sort(a+1,a+n*2+1,cmp); i=1; while (i<n*2) { if (a[i].y!=a[i+1].y) { re++; i++; } i++; } cout << re << endl; }
Code mẫu của happyboy99x
#include <cstdio> #include <algorithm> using namespace std; typedef pair<int, int> ii; ii p[200005]; int n; int main() { scanf( "%d", &n ); for( int i = 0; i < n; ++i ) { scanf( "%d", &p[i].first ); p[i].second = 0; } for( int i = n; i < (n<<1); ++i ) { scanf( "%d", &p[i].first ); p[i].second = 1; } sort(p, p+(n<<1)); bool skip = false; int cnt = 0; for( int i = 0; i < (n<<1)-1; ++i ) if ( skip ) skip = false; else if ( p[i].second != p[i+1].second ) { ++cnt; skip = true; } printf( "%d\n", cnt ); return 0; }
Code mẫu của ladpro98
program bwpoints; uses math; type e=record v,t:longint; end; const fi=''; maxN=222222; b=0;w=1; var a:array[1..maxN] of e; f:array[-1..maxN] of longint; n,res:longint; procedure input; var inp:text; i:longint; begin assign(inp,fi); reset(inp); readln(inp,n); for i:=1 to n do begin read(inp,a[i].v); a[i].t:=b; end; for i:=n+1 to 2*n do begin read(inp,a[i].v); a[i].t:=w end; close(inp); end; procedure swap(i,j:longint); var t:e; begin t:=a[i]; a[i]:=a[j]; a[j]:=t; end; procedure sort(l,r:longint); var p,i,j:longint; begin if l>=r then exit; p:=a[random(r-l+1)+l].v; i:=l;j:=r; repeat while a[i].v<p do inc(i); while a[j].v>p do dec(j); if i<=j then begin if i<j then swap(i,j); inc(i);dec(j); end; until i>j; sort(l,j);sort(i,r); end; procedure greedy; var i,black,white:longint; begin i:=1; while i<2*n do begin if a[i].t<>a[i+1].t then begin inc(res); inc(i,2); end else inc(i); end; end; begin input; sort(1,n*2); greedy; write(res); 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> #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); pair<int,int> a[200111]; int n, f[200111]; int main() { // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); scanf("%d", &n); FOR(i,1,n) { scanf("%d", &a[i].F); a[i].S = -1; } FOR(i,n+1,n+n) { scanf("%d", &a[i].F); a[i].S = 1; } n += n; sort(a+1, a+n+1); f[0] = 0; f[1] = 0; int res = 0; FOR(i,2,n) { if (a[i].S == a[i-1].S) f[i] = f[i-1]; else f[i] = max(f[i-1], 1 + f[i-2]); res = max(res, f[i]); } cout << res; return 0; }
Code mẫu của ll931110
#include <algorithm> #include <bitset> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <deque> #include <fstream> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <utility> #include <vector> using namespace std; int n; vector< pair<int,int> > v; int main() { // freopen("BWPOINTS.INP","r",stdin); // freopen("BWPOINTS.OUT","w",stdout); scanf("%d", &n); for (int i = 0; i < n; i++) { int x; scanf("%d", &x); v.push_back(make_pair(x,0)); } for (int i = 0; i < n; i++) { int x; scanf("%d", &x); v.push_back(make_pair(x,1)); } sort(v.begin(),v.end()); int col = -1,ret = 0; for (int i = 0; i < v.size(); i++) if (col < 0 || col == v[i].second) col = v[i].second; else { ret++; col = -1; } printf("%d\n", ret); }
Code mẫu của skyvn97
#include<stdio.h> #include<queue> using namespace std; int n; int c,k; typedef priority_queue<int,vector<int>,greater<int> > pq; pq b,w; void process(void) { int i,x; scanf("%d",&n); for (i=1;i<=n;i=i+1) { scanf("%d",&x); b.push(x); } for (i=1;i<=n;i=i+1) { scanf("%d",&x); w.push(x); } c=-1e9-1; k=0; while ((!b.empty()) && (!w.empty())) { k=k+1; c=max(b.top(),w.top()); while ((!b.empty()) && (b.top()<=c)) b.pop(); while ((!w.empty()) && (w.top()<=c)) w.pop(); } printf("%d",k); } int main(void) { process(); }
Comments