2102:合并果子
#include<bits/stdc++.h>
int n,a[10005],ans;
int main()
{
scanf("%d",&n);
for(int i=0;i< n;i++){
scanf("%d",&a[i]);
}
std::sort(a,a+n);
for(int i=1;i< n;i++){
ans += a[i-1]+a[i];
a[i]=a[i-1]+a[i];
for(int j=i+1;j<n;j++)
{
if(a[j-1]>a[j]) std::swap(a[j-1],a[j]);
else break;
}
}
printf("%d",ans);
return 0;
}
优先队列做法
//队列：将最小的拿出之后在将合并后的推入如此反复
#include<bits/stdc++.h>
using namespace std;
priority_queue<int,vector<int>,greater<int> >fruit; //优先队列，自动让队列中的元素由小到大排序
int main()
{
int n;
int total=0;//力气总量
int temp=0;
int theweightoffruit;//果子的重量
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&theweightoffruit);
fruit.push(theweightoffruit);//每输入一个果子的重量，他将由小到大排序
}
for(int i=0;i<n-1;i++){
temp=fruit.top();//弹出顶部元素，即最小的一堆
fruit.pop();//弹出当前最小的元素
temp+=fruit.top();//读取当前最小的一堆并与前一个元素合并
fruit.pop();//弹出第二小的元素
fruit.push(temp);//再将合并后的元素压入队列中
total+=temp;//那么花费的总力气再加上盒子里的就可以
}
printf("%d",total);
return 0;
}
2115: 区间选点（贪心）
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL ed,sum,n;
struct node{
LL l,r;
}a[100001];
//以右边界进行区间排序，并开始遍历区间
bool cmp(node x,node y){
return x.r<y.r;
}
int main(){
cin>>n;
for (int i = 1; i <= n; i++) {
cin>>a[i].l>>a[i].r;
}
sort(a+1,a+n+1,cmp);
//初始点ed=a[1].r sum=1
ed=a[1].r; sum=1;
for (int i = 1; i <= n; i++)
{
//用ed判断和a[i].l大小
//ed>a[i].l 说明该点能包含这个区间
//ed<a[i].l 说明该点包含不了
//ed=a[i].r sum++
if(ed<a[i].l)
{
sum++;
ed=a[i].r;
}
}
cout<<sum;
return 0;
}
2081: 盛水问题
#include<bits/stdc++.h>
using namespace std;
int n,height[105],maxWater;
int main() {
cin>>n;
for(int i=0;i<n;i++)
cin>>height[i];
//双指针
int left = 0;//左指针，初始指向数组的第一个元素
int right = n - 1; //右指针，初始指向数组的最后一个元素
// 当左指针小于右指针时，执行循环 ,否则指针无法移动
while (left < right) {
//获取当前两个指针所指向的垂线构成的容器的水量
int currentArea = min(height[left], height[right]) * (right - left);
// 更新最大水量（如果当前水量大于已知的最大水量）
maxWater = max(maxWater, currentArea);
// 判断哪个指针应该移动
// 如果左指针的高度小于右指针的高度，则移动左指针
// 因为如果移动右指针，新的高度一定不大于当前左指针的高度，而宽度又减小了，所以水量不可能增加
if (height[left] < height[right]) {
++left; // 移动左指针
} else {
--right; // 移动右指针
}
}
cout<<maxWater;
return 0;
}
1467: 【例85.1】 金银岛
#include <bits/stdc++.h>// 引用万能头文件
using namespace std;// 标准命名空间
//金银岛问题
/*
1、计算性价比 总价/总重
2、性价比排序 sort(性价比)
3、装入口袋
4、输出ans
*/
struct Node{
int w;//总重量
double all_p;//总价
double p; //单价
}a[105];
int n;
int p(Node n1,Node n2)
{
return n1.p>n2.p;
}
int main() {
cin>>n;
int b,s;
for (int i=1;i<=n;i++){
double ans=0;
cin>>b>>s;
for(int j=1;j<=s;j++){
cin>>a[j].w>>a[j].all_p;
a[j].p = a[j].all_p/(a[j].w*1.0);
}
sort(a+1,a+1+s,p);
int n=1;
while((b-a[n].w)>=0&&n<=s)
{
ans+=a[n].all_p;
b-=a[n].w;
n++;
}
if(b<a[n].w&&n<=s)
ans +=b*a[n].p;
printf("%.2lf\n",ans);
}
return 0;
}
2053: 楼间跳跃
#include<bits/stdc++.h>
using namespace std;
long long n,m;
struct node {
long long h;
long long v;
//重置小于号运算符
bool operator < (const node &x) const{
return v>x.v;//这里反写，保证默认为小根堆
}
};
node a[1000005];
priority_queue <node> q;//小根堆，维护拿走的价值
long long ans=0;
long long sum=0;//拿走的价值总数
long long cnt=0;//拿走的楼层总数
int main() {
cin>>n>>m;
m++;//加上第一步
for(int i=1;i<=n;i++){
cin>>a[i].h>>a[i].v;
a[i].h--;//去掉进入该楼的层
}
for(int i=1;i<=n;i++){
if (i>m) break;//达不到i栋楼
sum+=a[i].v;//进入第i栋楼拿走的第一个v
if (a[i].h>0){//还有没拿走的
sum+=a[i].v*a[i].h;//都拿走
q.push(a[i]);//入队
cnt+=a[i].h;//都加进去
}
while (q.size()&&cnt-q.top().h>=m-i){//多的减掉
cnt-=q.top().h;
sum-=q.top().h*q.top().v;
q.pop();
}
if (cnt>m-i){//如果还多
ans=max(ans,sum-q.top().v*(cnt-(m-i)));
}else{//不多
ans=max(ans,sum);
}
}
cout<<ans;
return 0;
}
1471: 练85.2 排队接水
#include <bits/stdc++.h>
using namespace std;
/*思路：要想平均等待时间最短，那就让接水时间短人的先接水
首先是将接水时间排序，由于输出数据要求排队顺序，
所以最好是用一个结构体储存排队打水人的序号和时间。*/
//定义一个结构体存储打水人的序号id和打水时间
struct stu{
int id;
double t;
}a[1005];
//sort的判断函数，a打水时间小于b打水时间，这样打水时间少的排在前面
bool cmp(stu a, stu b){
return a.t<b.t;
}
int main(){
int n;
scanf("%d",&n);//n个人排队打水
for(int i=1;i<=n;i++){
scanf("%lf",&a[i].t);//打水时间
a[i].id = i; //序号
}
sort(a+1,a+n+1,cmp);//打水时间由少到多排序
double wt=0.0;//总的等待时间
for(int i=1;i<n;i++){
wt+=(n-i)*a[i].t;//排队时，没有接到水的人都在等待
printf("%d ",a[i].id);
}
printf("%d\n",a[n].id);
printf("%.2lf",wt/n);
return 0;
}