• 信奥一本通 贪心算法 回顾

    文章目录

    写在前面

    之前看到一篇非常好的博客 ， 上面的一句话让我记忆很深 ，“事实上现在也有很多人认为贪心题必须要排序，但排序和贪心从来没有任何关系。重要的是，贪心只是一种思想，而排序只是为了降低时间复杂度。排序恰好契合了贪心一直选当前最优的思想，能够将每次重新找最优变为连续的从优到劣。堆经常被用来做贪心题亦是如此。如果一直想着“我应该按哪一维排序”或者“堆的排序关键字是什么”这种问题，而不想贪心究竟是为了什么，那就得不偿失了。”

    A 家庭作业

    家庭作业

    思路：满足贪心的无后效性 ， 我们考虑用贪心做
    但是如何贪心呢 ， 如果我们按照第一维时间排序
    那么我们可以找出一组反例是

    4
1 3
2 10
2 10
3 1

    • 1
    • 2
    • 3
    • 4
    • 5

    这样贪心选选到的是

    1 3
2 10
3 1

    • 1
    • 2
    • 3

    但显然最优答案是

    2 10
2 10
3 1

    • 1
    • 2
    • 3

    如果我们按照第二维价格贪心
    那么也能找出一组反例是

    4
1 9
2 8
2 10
3 7

    • 1
    • 2
    • 3
    • 4
    • 5

    这样选到的就是

    2 10
2 8
3 7

    • 1
    • 2
    • 3

    但是最优解是

    1 9
2 10
3 7

    • 1
    • 2
    • 3

    这时候我们就需要思考一下我们确实应该先按时间排序 ，保证先处理时间小的 ， 但是如果在后面时间大的里面出现了比前面方案更优的存在时，我们应该把前面的去掉

    例如

    4
1 3
2 10
2 10
3 1

    • 1
    • 2
    • 3
    • 4
    • 5

    先选 1 3
    再选 2 10
    然后选 2 10
    这时候我们发现选的个数超过了期限时间，而且2 10 明显 优于 1 3 ， 我们就把 1 3 卡掉，用 2 10 代替 1 3 ，当然了如果第三个是 2 2，我们肯定就不会替换 ， 用小根堆模拟这个过程
    最后选 3 1

    #include
using namespace std;
        
#define fi first
#define se second  
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef unsigned long long ull;
typedef long long ll;
const int N = 1e6+10;
const int NN = 1e5+100;
const int pp = 998244353;
typedef pair<int,int>PII;
const int inf = 2147483647;

struct node{
	int x,y;
}a[N];

bool cmp(node a,node b){
	return a.x<b.x||(a.x==b.x&&a.y>b.y);
}//按时间排序

int n;
priority_queue<int,vector<int>,greater<int>> q;//小根堆

int main(){
	
	IOS;
	
	cin>>n;
	
	for(int i=1;i<=n;i++){
		cin>>a[i].x>>a[i].y;
	}	
	
	sort(a+1,a+1+n,cmp);
	
	for(int i=1;i<=n;i++){
		q.push(a[i].y);
		while(q.size()>a[i].x) q.pop();
	}
	//q.size() 是当前要消耗的时间 ， a[i].x 是期限 ，当消耗时间大于期限的时候我们考虑替换
	
	int ans = 0;
	
	while(!q.empty()){
		ans += q.top();
		q.pop();
	}
	cout<<ans;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51

    B 智力大冲浪

    智力大冲浪

    思路与 A题相同，把选中的标记一下即可；

    C 加工生产调度

    思路：
    满足贪心的无后效性 ， 我们考虑如何贪心
    我们找一下两组之间的关系去推整体的关系

    假设

    a1 a2
b1 b2

    • 1
    • 2

    这个排序满足时间最小
    那一定有

    a 1 + m a x ( a 2 , b 1 ) + b 2 > = a 2 + m a x ( a 1 , b 2 ) + b 1 a1 + max(a2 , b1) + b2 >= a2 + max(a1 , b2) + b1 a1+max(a2,b1)+b2>=a2+max(a1,b2)+b1

    移项

    m a x ( a 2 , b 1 ) − a 2 − b 1 > = m a x ( a 1 , b 2 ) − a 1 − b 2 max(a2 , b1) -a2 -b1 >= max(a1 , b2) -a1 -b2 max(a2,b1)−a2−b1>=max(a1,b2)−a1−b2

    化简
    − m i n ( a 2 , b 1 ) > = − m i n ( a 1 , b 2 ) -min(a2 , b1) >= -min(a1 , b2) −min(a2,b1)>=−min(a1,b2)
    m i n ( a 2 , b 1 ) < = m i n ( a 1 , b 2 ) min(a2 , b1) <= min(a1 , b2) min(a2,b1)<=min(a1,b2)

    但是这个式子不满足严格弱序

    给出大佬的文章

    浅谈邻项交换排序的应用以及需要注意的问题

    记下结论了

    #include
using namespace std;
        
#define fi first
#define se second  
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef unsigned long long ull;
typedef long long ll;
const int N = 1e4+10;
const int NN = 1e5+100;
const int pp = 998244353;
typedef pair<int,int>PII;
const int inf = 2147483647;

int n,min1 = 1e9+10,min2 = 1e9+10;
int sum1 , sum2 , ans;

struct node{ 
	int a,b,id;
}a[N];

bool cmp(node x,node y){
	return min(x.a , y.b) < min(y.a ,x.b) || (min(x.a , y.b) == min(y.a , x.b) && x.a < y.a);
}

int main(){
	
	IOS;
	
	cin >> n;
	
	for(int i=1;i<=n;i++){
		cin >> a[i].a; 
	}
	
	for(int i=1;i<=n;i++){
		cin >> a[i].b; 
		a[i].id = i;
	}
	
	sort(a+1,a+1+n,cmp);
	
	int t1 = a[1].a , t2 = a[1].a + a[1].b;
	
	for(int i=2;i<=n;i++){
		t2 = max( t1 + a[i].a , t2 ) + a[i].b;
        t1 += a[i].a;
	}
	
	cout << t2 << "\n";
	
	for(int i=1;i<=n;i++){
		cout << a[i].id << " ";
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55

    D 喷水装置3(线段覆盖最少线段)

    喷水装置3

    每个喷头真正覆盖的位置是与草坪的交点 ， 知道了 喷头横坐标和半径后，我们就能算出每个喷头覆盖的真正范围，就变成了一个线段覆盖问题 ， 用最少的线段 ， 考虑贪心 ， 贪心思路是在合法的范围内选择右边界最远的地方，不断更新右边界直到覆盖完成 ，注意无法覆盖断开的情况

    #include
using namespace std;
        
#define fi first
#define se second  
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef unsigned long long ull;
typedef long long ll;
const int N = 1e5+10;
const int NN = 1e5+100;
const int pp = 998244353;
typedef pair<int,int>PII;
const int inf = 2147483647;

int t,n;
double len,w;

struct node{
	double l,r;
}a[N];

bool cmp(node a,node b){
	return a.l<b.l||(a.l==b.l&&a.r<b.r);
}

int main(){
	
	cin >> t;
	
	while(t--){
		
		cin >> n >> len >> w ;
		
		double x,r;
		int cnt=0;
		
		for(int i = 1 ;i <= n ; i++){
			cin>>x>>r;
			if(2*r>w){
				a[++cnt].l = x - sqrt(r*r-(w/2)*(w/2));
				a[cnt].r   = x + sqrt(r*r-(w/2)*(w/2));
//				cout<
			}
		}
		
		sort(a+1,a+1+cnt,cmp);
		
		a[++cnt].l = 1e9 + 10;
		a[cnt].r   = 1e9 + 10;
		
		//存下所有线段长度然后排序
		
//		for(int i=1;i<=cnt;i++){
//			cout<
//		}
		
		double now = 0,max1 = 0;
		int ans = 0,f = 1;
		
		for(int i=1;i<=cnt;   ){
			if(a[i].l <= now){
				max1=max(max1,a[i].r);
				i++;
			}else{
				if(now == max1){
					f = 0;
					break;
				}
				now = max1;
				max1 = 0;
				ans++; 
//				cout<< now << " " << ans << " " << i <<"\n";
				if(now >= len){
					break;
				}
			}
		}
		
		if( !f ) printf("-1\n");
		else printf("%d\n",ans);

		
	}
	
	
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87

    E. 活动安排(线段覆盖，覆盖最多段)

    活动安排
    贪心思路：
    放右端点最靠左的线段最好，从左向右放，右端点越小妨碍越少
    其他线段放置按右端点排序，贪心放置线段，即能放就放

    #include
using namespace std;
        
#define fi first
#define se second  
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef unsigned long long ull;
typedef long long ll;
const int N = 1e6+10;
const int NN = 1e5+100;
const int pp = 998244353;
typedef pair<int,int>PII;
const int inf = 2147483647;

int n;

struct node{
	int l,r;
}a[N];

bool cmp(node a,node b){
	return a.r<b.r;
}//越早结束越好

int main(){
	
	IOS;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i].l>>a[i].r;
	}
	sort(a+1,a+1+n,cmp);
	int now = 0,ans = 0;
	for(int i=1;i<=n;i++){
		if(a[i].l >= now){
			now = a[i].r;
			ans++;
		}
	}
	cout<< ans ;
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42

    F 种树

    种树

    思路：为了尽可能的少种树 ， 我们考虑尽可能把树种在重叠部分 ， 树会在两个线段的尾部重叠 ， 我们按照线段右边界进行排序 ，从线段右端开始种树，让重叠部分尽可能最大

    #include
using namespace std;
        
#define fi first
#define se second  
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef unsigned long long ull;
typedef long long ll;
const int N = 1e4+10;
const int NN = 1e5+100;
const int pp = 998244353;
typedef pair<int,int>PII;
const int inf = 2147483647;

int n,h;
// 两个区间可能会在前一个区间的尾部重叠，考虑每次先放尾部的尽可能多的放重叠部分

struct node{
	int l,r,res;
}a[N];

bool cmp(node a,node b){
	return a.r< b.r;
}

int vis[NN],ans;

int main(){
	cin>>n>>h;
	
	for(int i=1;i<=h;i++){
		cin>>a[i].l>>a[i].r>>a[i].res;
	}
	
	sort(a+1,a+1+h,cmp);
	
	for(int i=1;i<=h;i++){
		int res=0;
		for(int j=a[i].l;j<=a[i].r;j++){
			if(vis[j]) res++;
		}
		
//		cout<< a[i].res<<"\n";
		
		if(res >= a[i].res) continue;
		else a[i].res -= res;
		
		for(int j=a[i].r;j>=a[i].l && a[i].res;j--){ 
			if(!vis[j]){
//				cout<< j <<"\n";
				vis[j] = 1;
				a[i].res--;
				ans++;
			}
		}
	}
	
	cout<< ans ;
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60

    G 数列极差

    数列极差

    思路：我们模拟这个过程发现 ， 要想这个操作尽可能大 ，大数应该在后面操作 ， 尽可能小的话 ， 小的数尽可能在后面操作

    用大根堆和小根堆模拟操作即可

    #include
using namespace std;
        
#define fi first
#define se second  
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef unsigned long long ull;
typedef long long ll;
const int N = 1e6+10;
const int NN = 1e5+100;
const int pp = 998244353;
typedef pair<int,int>PII;
const int inf = 2147483647;

int n,m;
int a[N];
priority_queue<int,vector<int>,less<int>   > pmax;
priority_queue<int,vector<int>,greater<int>> pmin;
int maxx1(){
	while(pmin.size() > 1){
		int a = pmin.top();
		pmin.pop();
		int b = pmin.top();
		pmin.pop();
		pmin.push(a*b+1);
	}
	return (int)pmin.top();
}

int minn1(){
	while(pmax.size() > 1){
		int a = pmax.top();
		pmax.pop();
		int b = pmax.top();
		pmax.pop();
		pmax.push(a*b+1);
	}
	return (int)pmax.top();
}

int main(){
	
	cin>>n;
	
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		pmax.push(a[i]);
		pmin.push(a[i]);
	}
	
	cin>>n;
	
	int ans = maxx1() - minn1(); 
	
	cout<< ans;
	
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57

    H 数列分段

    数列分段
    思路：贪心 ， 每次尽量使所有段总和接近最大值

    #include
using namespace std;
        
#define fi first
#define se second  
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef unsigned long long ull;
typedef long long ll;
const int N = 1e6+10;
const int NN = 1e5+100;
const int pp = 998244353;
typedef pair<int,int>PII;
const int inf = 2147483647;

int n,m;
int a[N];

int main(){
	
	cin>>n>>m;
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	a[n+1] = 1e9+10;
	int now = 0 , ans = 0;
	for(int i=1;i<=n+1;i++){
		if(now + a[i] <= m){
			now += a[i];
		}else{
			ans++;
			now = a[i];
		}
	}
	cout<< ans;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33

    I 钓鱼

    我们要求最多钓到的鱼的数量 ， 我们可以贪心求解 ，但是现在最大的问题就是如何计算路径上的消耗 ， 我们不知道最远要走到那里也就无法进行贪心，这时候我们发现数据范围很小 ，我们可以暴力枚举最远的池塘然后进行贪心

    #include
using namespace std;
        
#define fi first
#define se second  
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef unsigned long long ull;
typedef long long ll;
const int N = 1e3+10;
const int NN = 1e5+100;
const int pp = 998244353;
typedef pair<int,int>PII;
const int inf = 2147483647;

int h,n,ans,max1;
int a[101];
int w[101];
int s[101];
priority_queue<PII,vector<PII>,less<PII>> q;
int main(){
	
	cin >> n >> h;
	
	h = h * 12;
	
	for(int i=1;i<=n;i++){
		cin >> a[i];
	}
	for(int i=1;i<=n;i++){
		cin >> w[i];
	}
	for(int i=1;i<n;i++){
		cin >> s[i];
		s[i] += s[i-1];
	}
	
	// 暴力枚举终点
	for(int i=1;i<=n;i++){
		
		int now = h;
		int ans = 0;
		now -= s[i-1];
		
//		cout << now << "\n";
		
		while(!q.empty()) q.pop();
		
		for(int j=1;j<=i;j++){
			q.push({a[j] , j});
		}
		
		while( now > 0 && !q.empty() ){
			PII t = q.top();
			q.pop();
			
			now--;
			
			if(t.fi == 0) break;
			
			ans += t.fi;
			
			t.fi = max(0 , t.fi - w[t.se]);
			
			if(t.fi != 0) q.push(t);
		}
		
		max1 = max(max1 , ans);
		
	}
	
	cout<< max1;
	return 0;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74

    J 均分纸牌

    均分纸牌

    我们假设 Ai 是第 i 堆原有的数量
    ave 是平均数
    Xi 是第 i 个人向左传递的数量

    当 xi > 0 代表 这个人向左传递 xi 个
    xi < 0 代表 这个人从左边借 xi 个

    那么 满足 A i + x i + 1 − x i = a v e Ai + x_{i+1}-x_i = ave Ai+xi+1​−xi​=ave
    移项 A i + x i + 1 − a v e = x i Ai + x_{i+1} - ave = x_i Ai+xi+1​−ave=xi​
    是否移动我们只要看每次 x i x_i xi​ 是否为 0 即可

    这个式子里我们不知道的就是 x i + 1 x_{i+1} xi+1​

    x i + 1 x_{i+1} xi+1​ 所代表的就是前 i 项与均值的差值的和 ， 维护一个前缀和即可

    #include
using namespace std;
        
#define fi first
#define se second  
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef unsigned long long ull;
typedef long long ll;
const int N = 1e3+10;
const int NN = 1e5+100;
const int pp = 998244353;
typedef pair<int,int>PII;
const int inf = 2147483647;

ll n,sum,ave,ans;
ll a[N];
ll c[N];

int main(){
	
	IOS;
	
	cin >> n;
	
	for(int i=1;i<=n;i++){
		cin >> a[i];
		sum += a[i];
	}
	
	ave = sum / n;
	
	for(int i=1;i<=n;i++){
		
		c[i] = -(a[i] - ave) + c[i-1];
		
		
		a[i] = a[i] - ave + c[i];
		
		if(a[i]) ans++;
	}
	
	cout<< ans;

	return 0;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46

    K 糖果传递

    这题是一个环形的均分纸牌

    上题的假设不变

    我们假设 Ai 是第 i 堆原有的数量
    ave 是平均数
    Xi 是第 i 个人向左传递的数量

    当 xi > 0 代表 这个人向左传递 xi 个
    xi < 0 代表 这个人从左边借 xi 个

    那么 满足 A i + x i + 1 − x i = a v e Ai + x_{i+1}-x_i = ave Ai+xi+1​−xi​=ave

    我们要求的答案就是 ∑ i = 1 n x i \sum_{i=1}^{n}x_i ∑i=1n​xi​

    A 1 + x 2 − x 1 = a v e A_1 + x_2-x_1 = ave A1​+x2​−x1​=ave
    A 2 + x 3 − x 2 = a v e A_2 + x_3-x_2 = ave A2​+x3​−x2​=ave
    A 3 + x 4 − x 3 = a v e A_3 + x_4-x_3 = ave A3​+x4​−x3​=ave

    A n + x 1 − x n = a v e A_n + x_1-x_n = ave An​+x1​−xn​=ave

    整理一下

    x 2 = x 1 + a v e − A 1 x_2 = x_1 +ave -A_1 x2​=x1​+ave−A1​
    x 3 = x 2 + a v e − A 2 x_3 = x_2 +ave -A_2 x3​=x2​+ave−A2​

    x n = x n − 1 + a v e − A n − 1 x_n = x_{n-1} +ave -A_{n-1} xn​=xn−1​+ave−An−1​

    把所有项用 x 1 x_1 x1​表示
    x 1 = x 1 x_1 = x_1 x1​=x1​
    x 2 = x 1 + a v e − A 1 x_2 = x_1 +ave -A_1 x2​=x1​+ave−A1​
    x 3 = x 1 + a v e − A 2 + a v e − A 1 x_3 = x_1 +ave -A_2+ave-A_1 x3​=x1​+ave−A2​+ave−A1​

    x n = x 1 − ∑ j = 1 i − 1 A j − a v e x_n = x_1-\sum_{j=1}^{i-1}{A_j-ave} xn​=x1​−∑j=1i−1​Aj​−ave

    c i = { 0  if  x = 1 ∑ j = 1 i − 1 A j − a v e  if  x > 1 c_i=

    {0 if x=1∑j=1i−1Aj−ave if x>1" role="presentation" style="position: relative;">{0 if x=1∑j=1i−1Aj−ave if x>1
    ci​={0∑j=1i−1​Aj​−ave​ if x=1 if x>1​

    x n = x 1 − c i x_n = x_1-c_i xn​=x1​−ci​

    a n s = ∑ i = 1 n ∣ x 1 − c i ∣ ans = \sum_{i=1}^{n}{|x_1-c_i|} ans=∑i=1n​∣x1​−ci​∣

    注意要加绝对值 ， c i c_i ci​ 明显是不变的 ，只要确定 x 1 x_1 x1​的值即可 ，整个图结构是环形的 ，可以取任意一个值作为 x 1 x_1 x1​ 要使整个答案最小

    货舱选址问题 ， 选中间的那个数

    #include
using namespace std;
        
#define fi first
#define se second  
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef unsigned long long ull;
typedef long long ll;
const int N = 1e6+10;
const int NN = 1e5+100;
const int pp = 998244353;
typedef pair<int,int>PII;
const int inf = 2147483647;

ll n,sum,ave,ans;
ll a[N];
ll c[N];

int main(){
	
	IOS;
	
	cin >> n;
	
	for(int i=1;i<=n;i++){
		cin >> a[i];
		sum += a[i];
	}
	
	ave = sum / n;
	
	for(int i=2;i<=n;i++){
		c[i] = c[i-1] + a[i-1] - ave;
	}
	
	sort(c+1,c+1+n);
	
	int now = c[(n+1)/2];
	
	for(int i=1;i<=n;i++){
		ans += abs(now - c[i]);
	}
	
	cout << ans;
	
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
  • 相关阅读:
    音视频服务架构演进
    短出行日渐成熟，电动两轮车迎来下半场
    这才是 SpringBoot 统一登录鉴权、异常处理、数据格式的正确打开姿势
    leetcode-hot100-矩阵
    react中预览excel表格
    2022年申请牛剑入学的IB学霸们的成绩多高？
    seq2seq翻译实战-Pytorch复现
    6G网络需求、架构及技术趋势
    JUC并发编程第六篇，带你了解Java内存模型JMM
    【CPP】string 类的模拟实现
  • 原文地址：https://blog.csdn.net/woshilichunyang/article/details/126654996