C++
章节7 贪心总结
伍衍 LV2 金丹期 LV 4 @ 2025-4-15 18:30:23

$T1$ 股票买卖

思路：卖法：峰值卖，谷值买。巧算：只要a[i]>a[i+1],就把ans加上a[i]-a[i+1]（我没用巧算）

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+50;
int a[N];
struct P{
    int x,y;
};
vector<P> b;
signed main(){
    int n;
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> a[i];
    }
    for(int i=1;i<=n;i++){
    	int j=i+1;
        while(a[j-1]<a[j]&&j<=n) j++;
        if(i!=j-1) b.push_back(P{a[i],a[j-1]});
        i=j-1;
	}
    int sum=0;
    for(int i=0;i<b.size();i++){
        sum+=b[i].y-b[i].x;
    }
    cout << sum;
}

$T2$ 防晒

思路：将所有奶牛按右边界maxSPF排序，对于每头奶牛，用满足条件的，SPF值最小的那瓶。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2.5e3+50;
pair<int,int> nx[N],sc[N];
bool cmp(pair<int,int> a,pair<int,int> b){
    return a.second<b.second;
}
bool cmp2(pair<int,int> a,pair<int,int> b){
    return a.first<b.first;
}
signed main(){
    int c,l;
    cin >> c >> l;
    for(int i=1;i<=c;i++){
        cin >> nx[i].first >> nx[i].second;
    }for(int i=1;i<=l;i++){
        cin >> sc[i].first >> sc[i].second;
    }
    sort(nx+1,nx+c+1,cmp);
    sort(sc+1,sc+l+1,cmp2);
    int cnt=0;
    for(int i=1;i<=c;i++){
        for(int j=1;j<=l;j++){
            if(nx[i].first<=sc[j].first&&sc[j].first<=nx[i].second&&sc[j].second!=0){
                // cout << i << " " << j << endl;
                // cout << nx[i].first << " " << nx[i].second << " " << sc[j].first << " " << sc[j].second << endl;
                sc[j].second--;
                cnt++;
                break;
            }
        }
    }
    cout << cnt;
}

$T3$ 畜栏预定

思路：首先将所有奶牛按开始时间排序，然后用小根堆维护畜栏，优先选结束时间最快的那一个，没有则新建一个插入。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e4+50;
struct PII{
	int first,second;
	PII(int f,int s):first(f),second(s){}
	bool operator<(const PII &T)const { return first>T.first;}// 小根堆的另一种写法，重定义
};
struct PI2{
	int first,second,num;
	bool operator<(const PI2 &T)const { return first<T.first;}
};
PI2 a[N];
priority_queue<PII> b;
int c[N],idx;
signed main(){
    int n;
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> a[i].first >> a[i].second;
        a[i].num=i;
    }
    sort(a,a+n);
    for(int i=0;i<n;i++){
        if(!b.size()){
            idx++;
            b.push(PII(a[i].second,idx));
            c[a[i].num]=idx;
//            cout << "---------------" << endl;
        }else{
            PII tp=b.top();
//            cout << "min:" << tp.first << " " << tp.second << endl;
            if(tp.first<a[i].first){
//            	cout << "POP!\n";
                b.pop();
//                cout << "push:" << a[i].second << " " << tp.second << endl;
                b.push(PII(a[i].second,tp.second));
                c[a[i].num]=tp.second;
            }else{
//            	cout << "NO POP!\n";
                idx++;
//                cout << "push:" << a[i].second << " " << idx << endl;
                b.push(PII(a[i].second,idx));
                c[a[i].num]=idx;
            }
//            cout << "---------------" << endl; 
        }
    }
    cout << idx << endl;
    for(int i=0;i<n;i++){
        cout << c[i] << endl;
    }
}

$T4$ 雷达设备

思路：首先，如果y坐标超出，则直接输出-1，否则先记录每个小岛可以被雷达覆盖的范围，再通过s记录每个可以用一个雷达覆盖的小岛组中，第一个小岛的右端点。最后输出s的变更次数请辅助代码理解

代码：

#include <bits/stdc++.h>
#define int long long
#define PII pair<double,double>
using namespace std;
const int N=1e3+50;
PII a[N];
signed main(){
	int n,d;
	cin >> n >> d;
    bool flag=0;
	for(int i=0;i<n;i++){
		int x,y;
		cin >> x >> y;
		if(y>d){
			flag=1;
            break;
		}
		double cd=sqrt(d*d-y*y);
		a[i]={x+cd,x-cd};//算出可被雷达覆盖的区间，存放顺序是先右后左
		// cout << a[i].second << " " << a[i].first << endl;
	}
    if(flag){
        cout << -1;
    }else{
	    sort(a,a+n);
        int ans=0;
		double s=-1e20;//s记录每个小岛组（可以用一个雷达覆盖的小岛称为雷达组）第一个区间的右端点 
        for(int i=0;i<n;i++){
            if(s<a[i].second){
                ans++;
                s=a[i].first;
            }
        }
        cout << ans; 
    }
}

$T5$ 国王游戏

思路：按左右手乘积排序，注意要高精度。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e4+50;
pair<int,int> a[N];
vector<int> to_vector(int x){
    vector<int> C;
    while(x){
        C.push_back(x%10);
        x/=10;
    }
    return C;
}
bool cmp2(vector<int> &A, vector<int> &B)
{
	if(A.size() != B.size())
		return A.size() > B.size();
	for(int i = A.size() - 1; i >= 0; i--)
		if(A[i] != B[i])
			return A[i] > B[i];
	return true;
}
vector<int> mul(vector<int> &A, int b)
{
	vector<int> C;
	int t = 0;
	for(int i = 0; i < A.size() || t; i++)
	{
		if(i < A.size()) t += A[i] * b;
		C.push_back(t % 10);
		t /= 10;
	}
	while(C.back() == 0 && C.size() > 1) 
		C.pop_back();	
	return C;
}
vector<int> div(vector<int> &A, int b)
{
	vector<int> C;
	int t = 0,r = 0;
	for(int i = A.size() - 1; i >= 0; i --)
	{
		t = r * 10 + A[i];
		C.push_back(t / b);
		r = t % b;
	}
	reverse(C.begin(), C.end());
	while(C.back() == 0 && C.size() > 1)
		C.pop_back();
	return C;
}
vector<int> max_vector(vector<int> A,vector<int> B){
	if(cmp2(A,B)) return A;
	return B;
}
signed main(){
    int n;
    cin >> n;
    for(int i=0;i<=n;i++){
        cin >> a[i].first >> a[i].second;
        a[i].second*=a[i].first;
        swap(a[i].first,a[i].second);
    }
    sort(a+1,a+n+1);
    vector<int> mx(1,0),cf(1,1);
    for(int i=0;i<=n;i++){
        if(i) mx=max_vector(mx,div(cf,a[i].first/a[i].second));
        cf=mul(cf,a[i].second);
    }
    for(int i=mx.size()-1;i>=0;i--){
        cout << mx[i];
    }
}

$T6$ 给树染色

思路：父节点优先染色，再将子节点进行合并。并保存染色顺序。等所有节点都染成一个点时，按照保存的顺序将各个节点依次染色，计算出花费的代价。

代码：

#include <bits/stdc++.h>
using namespace std;
int n,r;
const int N=3e3+50;
struct P{
    int father,size,num;
    double pj;
};
P a[N];
int find(){
    double mx=0;
    int xi=1;
    for(int i=1;i<=n;i++){
        if(i!=r&&a[i].pj>mx) mx=a[i].pj,xi=i;
    }
    return xi;
}
int main(){
    int ans=0;
    cin >> n >> r;
    for(int i=1;i<=n;i++){
        cin >> a[i].num;
        ans+=a[i].num;
        a[i].size=1;
        a[i].pj=a[i].num;
    }
    for(int i=1;i<n;i++){
        int a1,b;
        cin >> a1 >> b;
        a[b].father=a1;
    }
    for(int i=1;i<n;i++){
        int x=find(),y=a[x].father;
        ans+=a[y].size*a[x].num;
        for(int j=1;j<=n;j++){
            if(a[j].father==x) a[j].father=y;
        }
        a[x].pj=-1;
        a[y].size+=a[x].size;
        a[y].num+=a[x].num;
        a[y].pj=1.0*a[y].num/a[y].size;
    }
    cout << ans;
}

$T7$ 耍杂技的牛

思路：按两值相加的结果排序（从小到大）

代码：

#include <bits/stdc++.h>
#define int long long
#define w first
#define s second
#define PII pair<int,int>
using namespace std;
const int N=5e4+50;
PII a[N];
bool cmp(PII a1,PII b){
    return a1.w+a1.s<b.w+b.s;
}
signed main(){
    int n;
    cin >> n;
    for(int i=1;i<=n;i++) cin >> a[i].w >> a[i].s;
    sort(a+1,a+n+1,cmp);
    int fxz=-2e9,sum=0;
    for(int i=1;i<=n;i++){
        fxz=max(fxz,sum-a[i].s);
        sum+=a[i].w;
    }
    cout << fxz;
}

$T8$ 最大的和

思路：用两层循环枚举y坐标区间，通过前缀和算出值，x坐标范围按最大子串的方法求，前缀和为a[i][j]+=[i-1][j];

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=110;
int a[N][N];
signed main(){
    int n,ans=-2e9;
    cin >> n;
    for(int i=1;i<=n;i++){
    	for(int j=1;j<=n;j++){
    		cin >> a[i][j];
    		a[i][j]+=a[i-1][j];
		}
	}
	for(int i=1;i<=n;i++){
    	for(int j=i;j<=n;j++){
    		int qzh=0;
    		for(int k=1;k<=n;k++){
    			if(qzh<0) qzh=0;
    			qzh+=a[j][k]-a[i-1][k];
    			ans=max(ans,qzh);
			}
		}
	}
	cout << ans;
}

$T9$ 任务

思路：把机器和任务都优先按时间降序排列。随后找出每个任务可以用哪些机器完成。再用lower_bound()找出最没用的那台（时间和难度最小的那台），计算利润，增加数量，随后删除此机器。

代码：

#include <bits/stdc++.h>
#define int long long
#define x first
#define y second
#define PII pair<int,int>
using namespace std;
const int N=1e5+50;
PII a[N],b[N];
bool cmp(PII a,PII b){
    if(a.x==b.x) return a.y>b.y;
    return a.x>b.x;
}
signed main(){
    int n,m;
    while(cin >> n >> m){
        for(int i=1;i<=n;i++){
            cin >> a[i].x >> a[i].y;
        }for(int i=1;i<=m;i++){
            cin >> b[i].x >> b[i].y;
        }
        sort(a+1,a+n+1,cmp);
        sort(b+1,b+m+1,cmp);
        int i=1,j=1,sy=0,num=0;
        multiset<int> st;
        for(j=1;j<=m;j++){
            PII t=b[j];
            while(i<=n&&a[i].x>=t.x){
                st.insert(a[i++].y);
            }
            auto it=st.lower_bound(t.y);
            if(it!=st.end()){
                num++;
                sy+=500ll*t.x+2ll*t.y;
                st.erase(it);
            }
        }
        cout << num << " " << sy << endl;
    }
}

目前还没有评论...

章节7 贪心总结

$T1$ 股票买卖

$T2$ 防晒

$T3$ 畜栏预定

$T4$ 雷达设备

$T5$ 国王游戏

$T6$ 给树染色

$T7$ 耍杂技的牛

$T8$ 最大的和

$T9$ 任务

0 条评论

状态

开发

支持

关于

章节7 贪心总结

T1T1T1 股票买卖

T2T2T2 防晒

T3T3T3 畜栏预定

T4T4T4 雷达设备

T5T5T5 国王游戏

T6T6T6 给树染色

T7T7T7 耍杂技的牛

T8T8T8 最大的和

T9T9T9 任务

0 条评论

状态

开发

支持

关于

登录

$T1$ 股票买卖

$T2$ 防晒

$T3$ 畜栏预定

$T4$ 雷达设备

$T5$ 国王游戏

$T6$ 给树染色

$T7$ 耍杂技的牛

$T8$ 最大的和

$T9$ 任务