11.P1094 [NOIP2007 普及组] 纪念品分组
题目给出每个纪念品的价格并且要分组，每组最多只能包括两件纪念品， 每组纪念品的价格之和不能超过一个给定的整数，求最少的分组数目。
可以给这一些价格排个序，然后判断最小的价格和最大的价格的价格之和是否在给定的整数 \(w\) 以内，如果满足条件就可以把他们分在一起，接着再去看第二小和第二大的，以此类推；但如果不满足的话就只能让最大价格的单独一组，接着判断最小的价格和第二大价格的纪念品，以此类推。
#include<bits/stdc++.h>
using namespace std;
const int N=3e4;
int w,n,a[N+5],ans;
int main()
{
scanf("%d%d",&w,&n);
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
sort(a+1,a+n+1);
int l=1,r=n;
while(l<=r)
{
if(a[l]+a[r]<=w)++l,--r;//满足条件就把两个纪念品分在一组
else --r;//不满足就将价格大的纪念品单独分一组
++ans;
}
printf("%d",ans);
return 0;
}
12.P1102 A-B 数对
给出一串正整数数列以及一个正整数 \(C\)，要求计算出所有满足 \(A - B = C\) 的数对的个数（不同位置的数字一样的数对算不同的数对）。
这题用两个循环暴力枚举是会超时的，所以不能那样做。
题目既然已经给出了 \(C\) ，然后 \(A,B\) 两个数也给出来了，所以我们可以把式子转换成 \(C + B = A\) ，然后把循环里读入的数字看成 \(B\) ，已知 \(C,B\) ，那么相加就是 \(A\) 了，所以我们可以一开始先把每一个数读入，接着用一个 map 累计每个数的数量，接着再遍历一次整个数组，用 \(ans\) 累加 \(B+C\) 也就是前面累计的 \(A\) 的数量。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5;
int n,c,a[N+5];
ll ans;
map<ll,int>cnt;
int main()
{
scanf("%d%d",&n,&c);
for(int i=1;i<=n;++i)
scanf("%d",&a[i]),++cnt[a[i]];//累计A的数量
for(int i=1;i<=n;++i)
ans+=cnt[a[i]+c];//ans加上B+C=A的数量
printf("%lld",ans);
return 0;
}
13.P1105 平台
这题题目看了半天才懂
这题就是给出一些平台的高度以及这个平台最左端的坐标和最右端的坐标，然后假设有一个物品从这个每一个平台的最左端和最右端掉下去后会掉到哪个平台上。
这题可以假设这些平台在一个平面直角坐标系的第一象限上，然后画出来模拟一下（出于时间问题我就不画了）就可以知道这个物品只会掉到比目前平台高度要低且左边坐标在当前物品所在坐标的左边、右边坐标在当前物品所在坐标的右边的平台上。因为 \(N\) 的范围比较少，所以直接对每一个平台左边的坐标和右边的坐标从 \(1 \sim N\) 枚举每一个平台是否符合条件，并且高度最高的平台的编号即为答案。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3;
int n,h[N+5],l[N+5],r[N+5];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d%d%d",&h[i],&l[i],&r[i]);
h[0]=-114514;
for(int i=1;i<=n;++i)
{
int ans=0;
for(int j=1;j<=n;++j)
{
if(i==j)continue;
if(h[j]<h[i] && l[j]<l[i] && r[j]>l[i] && h[ans]<h[j])ans=j;
}
printf("%d ",ans);
ans=0;
for(int j=1;j<=n;++j)
{
if(i==j)continue;
if(h[j]<h[i] && l[j]<r[i] && r[j]>r[i] && h[ans]<h[j])ans=j;
}
printf("%d\n",ans);
}
return 0;
}
14. P1111 修复公路
这题是一道很简单的并查集板子题，不懂的可以去模板题的题解区学习。首先把输入的每条道路按照修好的时间从小到大排序，然后逐个遍历去修好它，然后如果到最后全部村庄都连在一起的话就输出当前道路修好的时间。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3,M=1e5;
struct road
{
int x,y,t;
}a[M+5];
bool cmp(road x,road y)
{
return x.t<y.t;
}
int n,m,f[N+5];
int find(int x)
{
return f[x]=(f[x]==x?x:find(f[x]));
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
f[i]=i;
for(int i=1;i<=m;++i)
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].t);
sort(a+1,a+m+1,cmp);
int cnt=n;
for(int i=1;i<=m;++i)
{
int A=find(a[i].x),B=find(a[i].y);
if(A!=B)f[B]=A,--cnt;
if(cnt==1){printf("%d",a[i].t);return 0;}
}
printf("-1");
return 0;
}
15.P1115 最大子段和
这道题是简单的贪心，直接用一个变量将每一个数相加，然后保存最大的答案，接着判断这个变量如果小于 0 ，也就是前面加的这一段数字的和小于 0 ，那我们不如舍弃这一段，将这个变量变为 0 ，这样可以使后面得到的答案最大。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5;
int n,x,a[N+5],tmp,ans=-0x3f3f3f3f;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
scanf("%d",&x);
tmp+=x,ans=max(ans,tmp);
if(tmp<0)tmp=0;
}
printf("%d",ans);
return 0;
}