# 算法竞赛进阶指南-0x07基本算法-贪心

Solution：

Code:

int n, m;
P a[2505];
map<int, int> mp;

int main(){
__;
cin >> n >> m;
for(int i = 1; i <= n; i ++)    cin >> a[i].fi >> a[i].se;
for(int i = 1; i <= m; i ++){
int x, y;
cin >> x >> y;
mp[x] += y;
}
sort(a + 1, a + n + 1);
mp[0] = mp[1001] = n;
int ans = 0;
for(int i = n; i >= 1; i --){
auto k = mp.upper_bound(a[i].se);
k --;
if(k->first >= a[i].fi){
ans ++;
if(-- k->second == 0)   mp.erase(k);
}
}
cout << ans << endl;
return 0;
}



Solution：

Code:

int n;
pair<P,int> v[50005];
priority_queue<P, vector<P>, greater<P> > q;
int ans[50005];

int main(){
__;
cin >> n;
for(int i = 1; i <= n; i ++){
cin >> v[i].fi.fi >> v[i].fi.se;
v[i].se = i;
}
sort(v + 1, v + n + 1);
for(int i = 1; i <= n; i ++){
if(q.empty() || q.top().fi >= v[i].fi.fi){
pair t = {v[i].fi.se, q.size() + 1};
ans[v[i].se] = t.se;
q.push(t);
}
else{
pair t = q.top();
q.pop();
t.fi = v[i].fi.se;
ans[v[i].se] = t.se;
q.push(t);
}
}
cout << q.size() << endl;
for(int i = 1; i <= n; i ++){
printf("%d\n", ans[i]);
}
return 0;
}



Solution：

- 如果当前区间包含最后一个选择的点，则直接跳过；
- 如果当前区间不包含最后一个选择的点，则在当前区间的右端点的位置选一个新的点；

Code:

int n;
double d;
pair<double, double> v[1005];

int main(){
__;
cin >> n >> d;
bool f = false;
for(int i = 1; i <= n; i ++){
double x, y;
cin >> x >> y;
if(y > d)   f = true;
v[i] = {x + sqrt(d * d - y * y), x - sqrt(d * d - y * y)};
}
if(f)   puts("-1");
else{
sort(v + 1, v + n + 1);
double pre = -3e9;
int ans = 0;
for(int i = 1; i <= n; i ++){
if(v[i].se > pre + eps){
ans ++;
pre = v[i].fi;
}
}
printf("%d\n", ans);
}
return 0;
}



Solution：

Code:

int n;
P v[1005];

void output(vector<int> a){
for(int i = a.size() - 1; i >= 0; i --){
cout << a[i];
}
cout << endl;
}

vector<int> mul(vector<int> a, int b){
vector<int> c;
int t = 0;
for(int i = 0; i < a.size(); i ++){
t += a[i] * b;
c.pb(t % 10);
t /= 10;
}
while(t)    c.pb(t % 10), t /= 10;
return c;
}

vector<int> div(vector<int> a, int b){
vector<int> c;
bool f = false;
int t = 0;
for(int i = a.size() - 1; i >= 0; i --){
t = t * 10 + a[i];
int x = t / b;
if(x || f){
f = true;
c.pb(x);
}
t %= b;
}
reverse(c.begin(), c.end());
return c;
}

vector<int> two_max(vector<int> a, vector<int> b){
if(a.size() > b.size()) return a;
if(b.size() > a.size()) return b;
if(vector<int>(a.rbegin(), a.rend()) > vector<int>(b.rbegin(), b.rend()))   return a;
return b;
}

int main(){
__;
cin >> n;
for(int i = 0; i <= n; i ++){
int a, b;
cin >> a >> b;
v[i] = {a * b, a};
}
sort(v + 1, v + n + 1);

vector<int> x(1, 1);
vector<int> ans(1, 0);

for(int i = 0; i <= n; i ++){
if(i)   ans = two_max(ans, div(x, v[i].fi / v[i].se));
x = mul(x, v[i].se);
}
output(ans);
return 0;
}



Solution：

Code:

#include <bits/stdc++.h>
using namespace std;

int n, u;
int ans;
struct node{
int s, num, fa;
double avg;
}nodes[1005];

int find(){
int res = 0;
double s = 0;
for(int i = 1; i <= n; i ++){
if(i != u && nodes[i].avg > s){
res = i;
s = nodes[i].avg;
}
}
return res;
}

int main(){
cin >> n >> u;
for(int i = 1; i <= n; i ++){
cin >> nodes[i].s;
nodes[i].num = 1;
ans += nodes[i].s;
nodes[i].avg = nodes[i].s;
}

for(int i = 1; i < n; i ++){
int a, b;
cin >> a >> b;
nodes[b].fa = a;
}

for(int i = 1; i < n; i ++){
int ver = find();
int fver = nodes[ver].fa;
nodes[ver].avg = -1;
ans += nodes[ver].s * nodes[fver].num;
for(int j = 1; j <= n; j ++){
if(nodes[j].fa == ver)
nodes[j].fa = fver;
}
nodes[fver].s += nodes[ver].s;
nodes[fver].num += nodes[ver].num;
nodes[fver].avg = (double)nodes[fver].s / nodes[fver].num;
}
cout << ans << endl;
return 0;
}