贪心

算法基础课

发布日期: 2023-04-11

更新日期: 2023-04-11

文章字数: 2.3k

阅读时长: 13 分

阅读次数:

贪心

每次选取局部最优解，最终会得到全局最优解

区间问题

区间选点

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 100010;

int n;
struct Range
{
    int l,r;
    bool operator < (const Range &W ) const {
        return r < W.r;
    }
}range[N];

/*
    1、将每个区间按照右端点排序
    2、从前往后依此枚举每个区间，若当前区间已经包含点，则直接pass；否则，选择当前区间的右端点
    
    */
int main()
{
    cin >> n;
    for(int i = 0 ; i < n ; i ++ )
    {
        int l, r;
        cin >> l >> r;
        range[i] = {l,r};
    }
    
    sort(range, range+n);
    
    int res = 0 ,ed = -2e9;
    for(int i = 0 ; i < n ; i ++ )
    {
        if(range[i].l > ed)
        {
            res ++ ;
            ed = range[i].r;
        }
    }
    
    cout << res << endl;
    return 0;
}

import java.io.*;
import java.util.*;

public class Main {
	public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	public static StreamTokenizer in = new StreamTokenizer(new InputStreamReader(System.in));
	public static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

	public static int nextInt() throws Exception {
		in.nextToken();
		return (int) in.nval;
	}

	public static int N = 100010;
	public static int n;
	public static Range ranges[] = new Range[N];

	public static void main(String[] args) throws Exception {
		n = nextInt();
		for(int i = 0 ; i < n; i ++ ) {
		    int l,r;
		    l = nextInt();
		    r = nextInt();
		    ranges[i] = new Range(l,r);
		}
		
		Arrays.sort(ranges,0,n);
		int res = 0, ed = (int)-2e9;
		for(int i = 0; i <  n ; i ++ ) {
			if(ranges[i].l > ed) {
				res ++ ;
				ed = ranges[i].r;
			}
		}
		
		out.print(res);
		out.flush();
	}
}

class Range implements Comparable<Range>{
	int l,r;
	public Range(int l,int r) {
		this.l = l;
		this.r = r;
	}
	@Override
	public int compareTo(Range o) {
		return this.r - o.r;
	}
	
	
}

最大不相交区间的数量

跟前一题代码相同

区间分组

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;

const int N = 100010;
int n;
struct Range
{
    int l,r ;
    bool operator < (const Range &W) const 
    {
        return l < W.l;
    }
}range[N];

int main()
{
    cin >> n;
    for(int i = 0 ; i < n ; i ++)
    {
        int a,b;
        cin >> a >> b;
        range[i] = {a,b};
    }
    
    sort(range,range+n);
    
    priority_queue<int,vector<int>,greater<int>> heap;//小根堆
    
    for(int i = 0 ; i < n ; i ++ )
    {
        auto it = range[i];
        if(heap.empty() || heap.top() >= it.l) heap.push(it.r); //添加新的一组
        else 
        {
            heap.pop();
            heap.push(it.r);
        }
    }
    
    cout << heap.size() << endl;
    return 0;
}

import java.io.*;
import java.util.*;

public class Main {
	public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	public static StreamTokenizer in = new StreamTokenizer(new InputStreamReader(System.in));
	public static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

	public static int nextInt() throws Exception {
		in.nextToken();
		return (int) in.nval;
	}

	public static int N = 100010;
	public static int n;
	public static Range[] ranges = new Range[N];

	public static void main(String[] args) throws Exception {
		n = nextInt();
		for (int i = 0; i < n; i++) {
		    int l,r;
		    l = nextInt();
		    r = nextInt();
		    ranges[i] = new Range(l,r);
		}

		Arrays.sort(ranges, 0, n);
		PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
		for(int i = 0 ; i < n ; i ++ ) {
			Range it = ranges[i];
			if(pq.isEmpty() || pq.element() >= it.l) pq.add(it.r);
			else {
				pq.remove();
				pq.add(it.r);
			}
		}
		out.print(pq.size());
		out.flush();
	}
}

class Range implements Comparable<Range> {
	int l, r;

	public Range(int l, int r) {
		this.l = l;
		this.r = r;
	}

	@Override
	public int compareTo(Range o) {
		return this.l - o.l;
	}

}

区间覆盖

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 100010;

int n;
struct Range
{
    int l,r;
    bool operator < (const Range &W) const 
    {
        return l < W.l;
    }
}range[N];

int main()
{
    int st,ed;
    cin >> st >> ed;
    cin >> n;
    for(int i = 0 ; i < n ; i ++ )
    {
        int a,b;
        cin >> a >> b;
        range[i] = {a,b};
    }
    
    sort(range,range+n);
    
    int res = 0;
    bool success = false;
    for(int i = 0 ; i < n ; i ++ )
    {
        int j = i ,r = -2e9;
        while(j < n && range[j].l <= st) //找到能覆盖st，且右端点最大的区间
        {
            r = max(r,range[j].r);
            j ++ ;
        }
        
        if(r < st)//找不到了，说明无解 
        {
            res = -1;
            break;
        }
        
        res ++;
        if(r >= ed) //走到头了，可以结束了
        {
            success = true;
            break;
        }
        
        st = r;
        i = j - 1;
    }
    
    if(!success) res = -1; //若结束后所得的区间未能完全覆盖，也会无解
    cout << res << endl;
    return 0;
}

import java.io.*;
import java.util.*;

public class Main {
	public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	public static StreamTokenizer in = new StreamTokenizer(new InputStreamReader(System.in));
	public static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

	public static int nextInt() throws Exception {
		in.nextToken();
		return (int) in.nval;
	}

	public static int N = 100010;
	public static int n;
	public static Range[] ranges = new Range[N];

	public static void main(String[] args) throws Exception {
		int st, ed;
		st = nextInt();
		ed = nextInt();
		n = nextInt();
		for (int i = 0; i < n; i++) {
			int l, r;
			l = nextInt();
			r = nextInt();
			ranges[i] = new Range(l, r);
		}

		Arrays.sort(ranges, 0, n);

		int res = 0;
		boolean success = false;
		for (int i = 0; i < n; i++) {
			int j = i, r = (int) -2e9;
			while (j < n && ranges[j].l <= st) {
				r = Math.max(r, ranges[j].r);
				j++;
			}

			if (r < st) {
				res = -1;
				break;
			}

			res++;
			if (r >= ed) {
				success = true;
				break;
			}
			st = r;
			i = j - 1;
		}
		if (!success)
			res = -1;
		out.print(res);
		out.flush();
	}
}

class Range implements Comparable<Range> {
	int l, r;

	public Range(int l, int r) {
		this.l = l;
		this.r = r;
	}

	@Override
	public int compareTo(Range o) {
		return this.l - o.l;
	}

}

Huffman树

合并果子

#include<iostream>
#include<algorithm>
#include<queue>

using namespace std;

int main()
{
    int n;
    cin >> n;
    
    priority_queue<int,vector<int>,greater<int>> heap;//小根堆
    while(n--)
    {
        int x;
        cin >> x;
        heap.push(x);
    }
    
    int res = 0;
    while(heap.size() > 1)
    {
        int a = heap.top() ; heap.pop();
        int b = heap.top() ; heap.pop();
        res += a + b;
        heap.push(a+b);
    }
    
    cout << res << endl;
    return 0;
}

import java.io.*;
import java.util.*;

public class Main {
	public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	public static StreamTokenizer in = new StreamTokenizer(new InputStreamReader(System.in));
	public static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

	public static int nextInt() throws Exception {
		in.nextToken();
		return (int) in.nval;
	}

	public static int N = 10010;
	public static int n;

	public static void main(String[] args) throws Exception {
        n = nextInt();
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
        for(int i = 0; i < n ; i ++ ){
            int x = nextInt();
            pq.add(x);
        }
        int res = 0;
        while(pq.size() > 1){
            int a = pq.element();
            pq.remove();
            int b = pq.element();
            pq.remove();
            res += a + b;
            pq.add(a+b);
        }
        out.print(res);
		out.flush();
	}
}

排序不等式

排队打水

#include<iostream>
#include<algorithm>
typedef long long ll;
using namespace std;

const int N = 100010;

int n,t[N];

int main()
{
    cin >> n;
    for(int i = 0 ; i < n ; i ++ ) cin >> t[i];
    sort(t,t+n);
    ll res = 0;
    for(int i = 0 ; i < n ; i ++ )
    {
        res += t[i] * (n-i-1);
    }
    
    cout << res << endl;
    return 0;
}

import java.io.*;
import java.util.*;

public class Main {
	public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	public static StreamTokenizer in = new StreamTokenizer(new InputStreamReader(System.in));
	public static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

	public static int nextInt() throws Exception {
		in.nextToken();
		return (int) in.nval;
	}

	public static int N = 100010;
	public static int n;
	public static int t[] = new int[N];

	public static void main(String[] args) throws Exception {
        n = nextInt();
        for(int i = 0 ; i < n ; i ++ ){
            t[i] = nextInt();
        }
        Arrays.sort(t,0,n);
        Long res = (long) 0;
        for(int i = 0; i < n ; i ++ ){
            res += t[i] * (n - i - 1);
        }
        out.print(res);
		out.flush();
	}
}

绝对值不等式

货仓选址

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 100010;
int n,a[N];

int main()
{
    cin >> n;
    for(int i = 0 ; i < n ; i ++ ) cin >> a[i];
    sort(a,a+n);
    int res = 0;
    for(int i = 0 ; i < n ; i ++ )
    {
        res += abs(a[i] - a[n/2]);
    }
    cout << res << endl;
    return 0;
}

import java.io.*;
import java.util.*;

public class Main {
	public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	public static StreamTokenizer in = new StreamTokenizer(new InputStreamReader(System.in));
	public static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

	public static int nextInt() throws Exception {
		in.nextToken();
		return (int) in.nval;
	}

	public static int N = 100010;
	public static int n;
	public static int a[] = new int[N];

	public static void main(String[] args) throws Exception {
        n = nextInt();
        for(int i = 0 ; i < n ; i ++ ){
            a[i] = nextInt();
        }
        Arrays.sort(a,0,n);
        int res = 0;
        for(int i = 0 ; i <n ; i ++ ){
            res += Math.abs(a[i] - a[n/2]);
        }
        out.print(res);
		out.flush();
	}
}

推公式

耍杂技的牛

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
typedef pair<int,int> PII;
int n;
PII cow[N];
int main()
{
    cin >> n;
    for(int i = 0 ; i < n ;  i++ )
    {
        int w,s;
        cin >> w >> s;
        cow[i] = {w+s,w};
    }
    
    sort(cow,cow+n);
    int res = -2e9,sum = 0;
    for(int i = 0 ; i < n ; i ++ )
    {
        int w = cow[i].second , s = cow[i].first - w;
        res = max(res,sum-s);
        sum += w;
    }
    cout << res << endl;
    return 0;
}

import java.io.*;
import java.util.*;

public class Main {
	public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	public static StreamTokenizer in = new StreamTokenizer(new InputStreamReader(System.in));
	public static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

	public static int nextInt() throws Exception {
		in.nextToken();
		return (int) in.nval;
	}

	public static int N = 100010;
	public static int n;
	public static Cow cows[] = new Cow[N];

	public static void main(String[] args) throws Exception {
		n = nextInt();
		for (int i = 0; i < n; i++) {
			int w, s;
			w = nextInt();
			s = nextInt();
			cows[i] = new Cow(w, s);
		}

		Arrays.sort(cows, 0, n);
		int sum = 0, res = (int) -2e9;
		for (int i = 0; i < n; i++) {
			int w = cows[i].w, s = cows[i].s ;
			res = Math.max(res, sum - s);
			sum += w;
		}
		out.print(res);
		out.flush();
	}
}

class Cow implements Comparable<Cow> {
	int w, s;

	public Cow(int w, int s) {
		this.w = w;
		this.s = s;
	}

	@Override
	public int compareTo(Cow o) {
		return this.w + this.s - o.w - o.s;
	}

}

时空复杂度分析

C++中1s计算次数为10^7 ~ 10^8次

int 4Byte

char 1Byte

double,long long 8Byte

64MB = 2 ^ 26 Byte ，因此最大可以开2^24个int，即1600_0000

wck

http://example.com/2023/04117610.html

本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 wck !

贪心

MapReduce

这是论文MapReduce:Simplified Data Processing on Large Clusters翻译及研读笔记

2023-04-17 论文阅读

MapReduce

算法（五）动态规划

y总算法基础课的第五章动态规划笔记，包括c++以及java版本的例题题解

2023-04-11 算法基础课

动态规划

算法（六）贪心

贪心

区间问题

区间选点

最大不相交区间的数量

区间分组

区间覆盖

Huffman树

合并果子

排序不等式

排队打水

绝对值不等式

货仓选址

推公式

耍杂技的牛

时空复杂度分析

你的赏识是我前进的动力