SDUT《 算法分析与设计》 实验三-贪心算法

SDUT《 算法分析与设计》 实验三-贪心算法

贪心算法

• A - 汽车加油问题
• B - 多元Huffman编码问题
• C - 装船问题
• D - 活动选择
• E - 最优合并问题
• F - 区间覆盖问题

A - 汽车加油问题

#include 
#include 
#include
#define ll long long
#define mem(a,b) memset(a,b,sizeof a)
#define ull unsigned long long
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(auto i=a;i<=b;++i)
#define bep(i,a,b) for(auto i=a;i>=b;--i)
#define lowbit(x) x&(-x)
#define PII pair
#define x first
#define y second
#define PLL pair
#define PI acos(-1)
#define pb push_back
#define eb emplace_back
const double eps = 1e-6;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const int N = 2e5 + 10;
const int M = 111;
int dx[]={-1, 0, 1, 0};
int dy[]={0, 1, 0, -1};
using namespace std;

int dp[N];

inline void solve(){
    int n,k;
    cin>>n>>k;
    for(int i=0;i<=k;i++) cin>>dp[i];
    int sum=n,res=0;
    for(int i=0;i<=k;i++){
        if(dp[i]>n){
            cout<<"No Solution!"<=dp[i]) sum-=dp[i];
        else sum=n-dp[i],res++;
    }
    cout<>t;
    while(t--) solve();
    return 0;
}

B - 多元Huffman编码问题

#include 
#include 
#include
#define ll long long
#define mem(a,b) memset(a,b,sizeof a)
#define ull unsigned long long
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(auto i=a;i<=b;++i)
#define bep(i,a,b) for(auto i=a;i>=b;--i)
#define lowbit(x) x&(-x)
#define PII pair
#define x first
#define y second
#define PLL pair
#define PI acos(-1)
#define pb push_back
#define eb emplace_back
const double eps = 1e-6;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const int N = 2e5 + 10;
const int M = 211;
int dx[]={-1, 0, 1, 0};
int dy[]={0, 1, 0, -1};
using namespace std;

ll a[N];
priority_queue,greater >minq;
priority_queuemaxq;

inline void solve(){
    int n,kk;
    cin>>n>>kk;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        maxq.push(a[i]);
        minq.push(a[i]);
    }
    ll maxn=0;
    while(maxq.size()>1){
        ll x=maxq.top();maxq.pop();
        ll y=maxq.top();maxq.pop();
        maxn+=x+y;
        maxq.push(x+y);
    }
    ll minn=0;
    while(minq.size()%(kk-1)!=1) minq.push(0);
    while(minq.size()>1){
        ll sum=0;
        for(int i=1;i<=kk;i++){
            sum+=minq.top();
            minq.pop();
        }
        minn+=sum;
        minq.push(sum);
    }
    cout< 
C - 装船问题 
#include 
#include 
#include
#define ll long long
#define mem(a,b) memset(a,b,sizeof a)
#define ull unsigned long long
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(auto i=a;i<=b;++i)
#define bep(i,a,b) for(auto i=a;i>=b;--i)
#define lowbit(x) x&(-x)
#define PII pair
#define x first
#define y second
#define PLL pair
#define PI acos(-1)
#define pb push_back
#define eb emplace_back
const double eps = 1e-6;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const int N = 2e5 + 10;
const int M = 111;
int dx[]={-1, 0, 1, 0};
int dy[]={0, 1, 0, -1};
using namespace std;

struct node{
    int p,w,d;
}dp[N];

bool cmp(node x,node y){
    return x.d>y.d;
}

inline void solve(){
    int n;
    cin>>n;
    for(int i=1;i<=10;i++){
        cin>>dp[i].p>>dp[i].w;
        dp[i].d=dp[i].p/dp[i].w;
    }
    sort(dp+1,dp+11,cmp);
    int sum=0;
    for(int i=1;i<=10;i++){
        if(dp[i].w<=n) sum+=dp[i].p,n-=dp[i].w;
        else{
            sum+=dp[i].d*n;
            break;
        }
    }
    cout<>t;
    while(t--) solve();
    return 0;
}
 
D - 活动选择 
#include 
#include 
#include
#define ll long long
#define mem(a,b) memset(a,b,sizeof a)
#define ull unsigned long long
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(auto i=a;i<=b;++i)
#define bep(i,a,b) for(auto i=a;i>=b;--i)
#define lowbit(x) x&(-x)
#define PII pair
#define x first
#define y second
#define PLL pair
#define PI acos(-1)
#define pb push_back
#define eb emplace_back
const double eps = 1e-6;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const int N = 2e5 + 10;
const int M = 111;
int dx[]={-1, 0, 1, 0};
int dy[]={0, 1, 0, -1};
using namespace std;

struct  node{
    int s,e,id;
}dp[N];

bool cmp(node x,node y){
    if(x.e>n;
    for(int i=1;i<=n;i++){
        cin>>dp[i].s>>dp[i].e;
        dp[i].id=i;
    }
    sort(dp+1,dp+1+n,cmp);
    int e=0;
    int res[M];
    int tot=0;
    for(int i=1;i<=n;i++){
        if(dp[i].s>=e){
            e=dp[i].e;
            res[++tot]=dp[i].id;
        }
    }
    bool tag=0;
    for(int i=1;i<=tot;i++){
        if(tag) cout<<",";
        else tag=1;
        cout<>t;
    while(t--) solve();
    return 0;
}
 
E - 最优合并问题 
#include 
#include
#define ll long long
using namespace std;

inline void solve(){
    int n;
    cin>>n;
    priority_queue,greater >q1;
    priority_queueq2;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        q1.push(x);
        q2.push(x);
    }
    int sum1=0,sum2=0;
    while(q1.size()>1){
        int a=q1.top();q1.pop();
        int b=q1.top();q1.pop();
        sum1+=a+b-1;
        q1.push(a+b);
    }
    while(q2.size()>1){
        int a=q2.top();q2.pop();
        int b=q2.top();q2.pop();
        sum2+=a+b-1;
        q2.push(a+b);
    }
    cout< 
F - 区间覆盖问题 
#include 
#include
#define ll long long
using namespace std;

setst;

inline void solve(){
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        st.insert(x);
    }
    int tot=0;
    int pos=INT_MIN;
    for(auto i:st){
        if(i>=pos&&i<=pos+k) continue;
        else{
            tot++;
            pos=i;
        }
    }
    cout<					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5579812.html