【学习笔记PPT摘录】lan.289.24.4-15

1.纪念品分组.双指针-01

在这里插入图片描述

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

int A[40000];
  // 纪念品价值均衡
  // 把购来的纪念品进行分组 之和不超过整数 w
  // 每组只能有两个纪念品 希望分组的数目要少

  // 贪心的策略就是 每个较大的数找到一个 最大的较小的数使其能够小于w
  // n为个数

  // 利用双指针 一个从前向后
  
int main()
{
  int w,n;cin>>w>>n;
  for(int i=1;i<=n;i++){
    cin>>A[i];
  }
  sort(A+1,A+1+n);
  int ans=0;
  int i=1;int j=n;
  while(i<=j){
    // cout<<A[i]<<" "<<A[j]<<endl;
      if(A[i]+A[j]<=w){
        i++;j--;
        ans++;
      }else{
        j--;
        ans++;
      }
  }
  cout<<ans;

  // 请在此输入您的代码
  return 0;
}

2.珠宝的最大交替和

在这里插入图片描述


#include<iostream>
using namespace std;
typedef long long ll;
ll n;
const int N = 2E5;
ll a[N], b[N];
int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		if (i % 2 == 0)b[i] = (0 - abs(a[i]));//表示是偶数
		else b[i] = abs(a[i]);//b[i]存放实际数据
	}
	ll Min1 = b[1], Min2 = b[2];//找到正数中的最小值，负数中的最小值
	ll j1=1, j2=2;
	for (int i = 1; i <= n; i++)
	{
		if (i % 2 != 0)//正数
		{
			if (b[i] < Min1)
			{
				Min1 = b[i];
				j1 = i;//纪录最小整数位置  4 ；  1
			}
		}
		else
		{
			if (b[i] < Min2)
			{
				Min2 = b[i];
				j2 = i;//纪录最大整数位置 -3
			}
		}
	}
	ll sum = 0;
	if (abs(Min2) >= Min1)  //3 > 1  //
	{
		ll t=0;
		t=b[j1];
		b[j1]=0-b[j2];
		b[j2]=0-t;	
	}
	
	
	for (int i = 1; i <= n; i++)
	{
//		if (abs(Min2) >= Min1)  //3 > 1
//		{
//			if (i == j1)
//			{
//				sum += 0 - b[i];
//				continue;
//			}
//			if (i == j2)
//			{
//				sum += 0 - b[i];
//				continue;
//			}
//		}
		sum += b[i];
	}
	cout << sum;
	return 0;
}

func 2

#include<bits/stdc++.h>
#define endl '\n' 
#define ll long long
using namespace std;

ll ans = 0;
int inf = 1 << 30;

void solve()
{
	int n;
	int c = -inf,d = inf;
	cin >> n;
	vector<int> a(n);
	for(int i = 0;i < n;i ++){
		cin >> a[i];
		a[i] = abs(a[i]);
		if(i & 1) c = max(c,a[i]),ans -= a[i];
		else d = min(d,a[i]),ans +=a[i];
	}
	if(c > d) ans += 2 * (c - d);
	cout << ans << endl;
	
}


int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int _; // cin >> _;
	_ = 1;
	while(_ --) solve();
	
	return 0;
}