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;
}
3. 小蓝的礼物 --模拟 排序-2*
这里求的是最多可以购买多少件。嗯，有一个思路就是先把他们所有的都给排一个序。然后呢？开始统计前N项的和，以及第N加一项1/2的。价格。总共可以买到N加一箱啦。但是也有一个问题，那么前面的N像这个N该如何确定呢？
c
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
int n[N];void slove(){int a,b,cnt=0;cin>>a>>b;//这里的a是商品件数，这里的B是总的钱数。 for(int i=0;i<a;i++){cin>>n[i];cnt+=n[i]; //这个指的是所有产品的总价钱。}sort(n,a+n);int ans,jud;ans=a;for( int i=a-1;i>=0;--i){jud=cnt;jud=jud-n[i]/2;if(jud<=b){break;}cnt-=n[i];ans--;}cout<<ans;}
signed main(){int num=1;while(num--){slove();}return 0;
}最值查找-
自上而下树形DP_ -
状压DP_ -_
选择排序_-_
线性DP_ -
位运算_ -
完全背包_ -_
桶排序_-_
贪心-
双指针_ -_
数位DP_ -_
输入输出_ -
全排列-_
区间DP_ -
前缀和_ -_
其他库函数-蓝
