目录
介绍：
题目一：
题目二：
题目三：
题目四：
题目五：
题目六：
题目七：
题目八：
介绍：
贪心算法是一种特殊的算法思想，它在每一步选择中都采取当前状态下最优的选择，从而希望达到全局最优的解。贪心算法的基本思路是通过贪心策略进行选择，每次选择都是局部最优的，但不能保证最终达到全局最优。
贪心算法的适用条件是问题具有贪心选择性质，即通过局部最优解可以得到全局最优解。而且贪心选择性质要能够推导出最优解的正确性。
贪心算法的步骤通常包括以下几个步骤：
1. 将问题分解成若干个子问题，问题的解可以通过这些子问题的解来构造；
2. 确定贪心选择，即每一步的最优选择；
3. 通过贪心选择得到最优解的一个部分，加入到问题的解中；
4. 对剩余的子问题进行相同的处理，直到所有子问题都被解决。贪心算法的优点是简单、高效，但缺点是不能保证得到全局最优解。因此，在使用贪心算法时需要注意问题的特性，以确定贪心选择的正确性。同时，贪心算法通常作为其他算法的辅助算法使用，例如在动态规划中使用贪心选择来简化问题。
题目一：
#include<iostream>
#include<cstring>
using namespace std;
int a[1010];
int flag[1010];//记录第i个问题放的箱子号
int v[1010];
int main()
{
int n, cnt = 1;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
int flags = 0;
for (int j = 1; j <= cnt; j++)
{
if (v[j] + a[i] <=100)//第j个箱子已有的加上该物体装不满100，则加入该箱子
{
flag[i] = j, flags = 1, v[j] += a[i];
break;
}
}
if (flags == 0)//已有箱子不够，再开一个箱子
flag[i] = cnt + 1, cnt++,v[cnt]=a[i];
}
for (int i = 1; i <= n; i++)
cout << a[i] << " " << flag[i] << endl;
cout << cnt << endl;
}题目二：
#include<iostream>
#include<cstring>
using namespace std;
int main()
{
int n,k;
cin>>n>>k;
int a[1010];
for(int i=1;i<=k+1;i++)
{
cin>>a[i];
}
int cnt=0,flag=1;
int tmp=n;//表示还可以行驶的公里
for(int i=1;i<=k+1;i++)
{
if(tmp<a[i])//不够行驶到下一个加油站
{
flag=0;//标记为无法到达终点
break;
}
if(tmp-a[i]-a[i+1]<0)//是否可以不经过该加油站能到达下一个加油站
{
cnt++;//不可以，说明，要在该加油站加油，数量加一
tmp=n;//公里数回到n
}
else
{
tmp-=a[i];//减去该次的公里数
}
}
if(flag==1)
cout<<cnt<<endl;
else
cout<<"No Solution!"<<endl;
}题目三：
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int main()
{
int s[1010], e[1010], n;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> s[i] >> e[i];
}
sort(s + 1, s + 1 + n);//递增
sort(e + 1, e + 1 + n);//递增
int cnt = 1;//初始一个，因为开始时间从第二个开始
int j = 1;//代表结束时间
for (int i = 2; i <= n; i++)//开始时间从第二个开始遍历
{
if (e[j] > s[i])//开始时间小于上一个结束时间
{
cnt++;//会场加一
}
else//开始时间大于上一个结束时间，该会场可以容纳
j++;
}
cout << cnt<<endl;
}题目四：
#include<iostream>
#include<algorithm>
using namespace std;
bool cmp(int a,int v)
{return a>v;}
int main()
{
int n;
int a[101000],b[101000];
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
b[i]=a[i];
}
int ma=0;
for(int i=1;i<=n-1;i++)
{
sort(a+i,a+1+n,cmp);//从大到小排序，取最大的两个相加
a[i+1]+=a[i];
ma+=a[i+1]-1;
}
cout<<ma<<" ";
int mn=0;
for(int i=1;i<=n-1;i++)
{
sort(b+i,b+1+n);//从小到大排序，取最小的两个
b[i+1]+=b[i];
mn+=b[i+1]-1;
}
cout<<mn<<endl;
}题目五：
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int n;
while (cin >> n)
{
int flag1 = 0, flag2 = 0;
int a[1100], b[1100];
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
for (int i = 1; i <= n; i++)
{
cin >> b[i];
}
sort(a + 1, a + 1 + n);//递增
sort(b + 1, b + 1 + n);
for(int i=1;i<=n/2;i++)//a的前一半与b的后一半比较
{
if(a[i]>b[n/2+i])
flag1++;
else
flag2++;
}
for(int i=1;i<=n/2;i++)//b的前一半与a的后一半比较
{
if(b[i]>a[n/2+i])
flag2++;
else
flag1++;
}
if (n%2!=1&&flag1 == flag2)
cout << "YES" << endl;
else
cout << "NO" << endl;
}
}题目六：
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int n,l;
cin>>n>>l;
int a[1010];
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
sort(a+1,a+n+1);//从小到大排序
int cnt=0;
for(int i=1;i<=n;i++)
{
if(l-a[i]>=0)
{
cnt++;
l-=a[i];
}
}
cout<<cnt<<endl;
}题目七：
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int main()
{
int s[1010], e[1010], n;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> s[i] >> e[i];
}
sort(s + 1, s + 1 + n);//递增
sort(e + 1, e + 1 + n);//递增
int cnt = 1;//初始一个，因为开始时间从第二个开始
int j = 1;//代表结束时间
for (int i = 2; i <= n; i++)//开始时间从第二个开始遍历
{
if (e[j] > s[i])//开始时间小于上一个结束时间
{
cnt++;//会场加一
}
else//开始时间大于上一个结束时间，该会场可以容纳
j++;
}
cout << cnt<<endl;
}题目八：
#include<iostream>
#include<cmath>
using namespace std;
int n, n0, n1;
int min1 = 99999;
int a1, b1;//女生、男生宿舍人数
int judge(int k)//女生分k个宿舍
{
if (n0 % k != 0)//不能平均分
return 0;
if(n0==k)//不能一个人一间
return 0;
if (n1 % (n - k) != 0)//不能均分
return 0;
if(n1==(n-k))//不能一个人一间
return 0;
int a = n0 / k, b = n1 / (n - k);
if (min1 > abs(a - b))
{
min1 = abs(a - b);
a1 = a, b1 = b;
}
return 1;
}
int main()
{
cin >> n0 >> n1 >> n;
for (int i = 1; i <= n-1; i++)
judge(i);
if (min1 != 99999)
cout << n0 / a1 << " " << n1 / b1 << endl;
else
cout << "No Solution" << endl;
}
