5.15离散化

P1496 火烧赤壁

#include<bits/stdc++.h>
using namespace std;
const int N = 20010;
typedef pair<int, int> PII;
struct node{int l, r;
}a[N];
bool cmp(node a, node b){if(a.l != b.l)return a.l < b.l;return a.r < b.r;
}
void solve(){int n; cin >> n;for(int i = 1; i <= n; i++){cin >> a[i].l >> a[i].r;}sort(a + 1, a + n + 1, cmp);vector<PII> v;v.push_back({a[1].l, a[1].r});for(int i = 2; i <= n; i++){auto t = v.back();int l1 = t.first, r1 = t.second;if(a[i].r <= r1)continue;if(a[i].l >= r1){v.push_back({a[i].l, a[i].r});continue;}v.pop_back();v.push_back({l1, a[i].r});}int sum = 0;for(auto t : v){int len = t.second - t.first;sum += len;}cout << sum << endl;
} 
signed main()
{ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);solve();return 0;
}

离散化

#include<bits/stdc++.h>
using namespace std;
int c[40010], f[40010];
void solve(){int n, a[20010], b[20010], k = 1, ans = 0;cin >> n;for(int i = 1; i <= n; i++){cin >> a[i] >> b[i];c[k++] = a[i];c[k++] = b[i];}sort(c + 1, c + 1 + 2 * n);for(int i = 1; i <= n; i++){a[i] = lower_bound(c + 1, c + 2 * n + 1, a[i]) - c;b[i] = lower_bound(c + 1, c + 2 * n + 1, b[i]) - c;for(int j = a[i]; j < b[i]; j++)f[j] = 1;}for(int i = 1; i < 2 * n; i++){if(f[i])ans += c[i + 1] - c[i];}cout << ans << endl;
}
signed main()
{ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);solve();return 0;
}

P1904 天际线

#include<bits/stdc++.h>
using namespace std;void solve(){int a[5010], b[5010], h[5010], cnt = 0, c[10010], k = 0;int f[10010] = {}, ans[15010];while(cin >> a[cnt] >> h[cnt] >> b[cnt]){c[k++] = a[cnt];c[k++] = b[cnt];cnt++;}sort(c, c + k);for(int i = 0; i < cnt; i++){a[i] = lower_bound(c, c + k, a[i]) - c;b[i] = lower_bound(c, c + k, b[i]) - c;for(int j = a[i]; j < b[i]; j++){if(f[j] < h[i])f[j] = h[i];}}ans[0] = c[0];int x = 1;for(int i = 1; i <= k; i++){if(f[i] != f[i - 1]){ans[x++] = f[i - 1];ans[x++] = c[i];}}for(int i = 0; i < x; i++)cout << ans[i] << " ";cout << 0 << endl;
}
signed main()
{ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);solve();return 0;
}

P1884 [USACO12FEB] Overplanting S

#include<bits/stdc++.h>
using namespace std;
struct node{int x1, y1, x2, y2;
}rect[1010];
bool c[2010][2010];
void solve(){int n, a[2010], b[2010];long long ans = 0;cin >> n;for(int i = 0; i < n; i++){cin>> rect[i].y1 >> rect[i].x2 >> rect[i].y2 >> rect[i].x1;a[i * 2] = rect[i].x1;a[i * 2 + 1] = rect[i].x2;b[i * 2] = rect[i].y1;b[i * 2 + 1] = rect[i].y2;}sort(a, a + 2 * n);int lena = unique(a, a + 2 * n) - a;sort(b, b + 2 * n);int lenb = unique(b, b + 2 * n) - b;for(int i = 0; i < n; i++){rect[i].x1 = lower_bound(a, a + lena, rect[i].x1) - a;rect[i].x2 = lower_bound(a, a + lena, rect[i].x2) - a;rect[i].y1 = lower_bound(b, b + lenb, rect[i].y1) - b;rect[i].y2 = lower_bound(b, b + lenb, rect[i].y2) - b;for(int j = rect[i].x1; j < rect[i].x2; j++){for(int k = rect[i].y1; k < rect[i].y2; k++){c[j][k] = 1;}}}for(int i = 0; i < lena - 1; i++){for(int j = 0; j < lenb - 1; j++){if(c[i][j])ans += (long long)(a[i + 1] - a[i]) * (b[j + 1] - b[j]);}}cout << ans << endl;
}
signed main()
{ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);solve();return 0;
}

P3029 [USACO11NOV] Cow Lineup S

#include<bits/stdc++.h>
using namespace std;
const int N = 500010;
struct node{int pos, type;
}a[N];
bool cmp(node a, node b){return a.pos < b.pos;
}
void solve(){int n, head = 0, x = 0, ans = 2e9;cin >> n;map<int, int> mp;for(int i = 0; i < n; i++){cin >> a[i].pos >> a[i].type;mp[a[i].type] = 1;}int len = mp.size();sort(a, a + n, cmp);for(int i = 0; i < n; i++){mp[a[i].type]++;if(mp[a[i].type] == 2)x++;while(x == len){ans = min(ans, a[i].pos - a[head].pos);mp[a[head].type]--;if(mp[a[head].type] == 1)x--;head++;}}cout << ans << endl;
} 
signed main()
{ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);solve();return 0;
}