洛谷-算法1-5-贪心2

故事和你91

778人浏览 · 2026-04-12 16:57:07

故事和你91 · 2026-04-12 16:57:07 发布

P3817 小A的糖果

题目描述

小 A 有 n 个糖果盒，第 i 个盒中有 ai 颗糖果。

小 A 每次可以从其中一盒糖果中吃掉一颗，他想知道，要让任意两个相邻的盒子中糖的个数之和都不大于 x，至少得吃掉几颗糖。

输入格式

输入的第一行是两个用空格隔开的整数，代表糖果盒的个数 n 和给定的参数 x。

第二行有 n 个用空格隔开的整数，第 i 个整数代表第 i 盒糖的糖果个数 ai。

输出格式

输出一行一个整数，代表最少要吃掉的糖果的数量。

输入输出样例

输入 #1复制

3 3
2 2 2

输出 #1复制

输入 #2复制

6 1
1 6 1 2 0 4

输出 #2复制

输入 #3复制

5 9
3 1 4 1 5

输出 #3复制

说明/提示

样例输入输出 1 解释

吃掉第 2 盒中的一个糖果即可。

样例输入输出 2 解释

第 2 盒糖吃掉 6 颗，第 4 盒吃掉 2 颗，第 6 盒吃掉 3 颗。

数据规模与约定

对于 30% 的数据，保证 n≤20，ai,x≤100。
对于 70% 的数据，保证 n≤103，ai,x≤105。
对于 100% 的数据，保证 2≤n≤105，0≤ai,x≤109

实现代码

#include<bits/stdc++.h>
using namespace std;
long long a[100005];
long long sum;

int main(){
	int n,x;
	cin>>n>>x;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	if(a[1]>x){
		sum+=a[1]-x;
		a[1]=x;
	}
	for(int i=2;i<=n;i++){
		if(a[i]+a[i-1]>x){
			sum+=a[i]+a[i-1]-x;
			a[i]=x-a[i-1];
		}
	}
	cout<<sum;
	return 0;
}

P1106 删数问题

题目描述

键盘输入一个高精度的正整数 n（不超过 250 位），去掉其中任意 k 个数字后剩下的数字按原左右次序将组成一个新的非负整数。编程对给定的 n 和 k，寻找一种方案使得剩下的数字组成的新数最小。

输入格式

输入两行正整数。

第一行输入一个高精度的正整数 n。

第二行输入一个正整数 k，表示需要删除的数字个数。

输出格式

输出一个整数，最后剩下的最小数。

输入输出样例

输入 #1复制

175438 
4

输出 #1复制

说明/提示

用 len(n) 表示 n 的位数，保证 1≤k<len(n)≤250。

注意：去掉若干数字后剩下的数可以存在前导零，而输出时不要输出前导零。

实现代码

#include<bits/stdc++.h>
using namespace std;
int a[255];

int main(){
	string s;
	int n;
	cin>>s;
	cin>>n;
	int len=s.size();
	for(int i=0;i<len;i++){
		a[i]=s[i]-'0';
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<len;j++){
			if(a[j]>a[j+1]){
				for(int k=j;k<len;k++){
					a[k]=a[k+1];
				}
				len--;
				break;
			}
		}
	}
	int ax=0,ac=0;
	while(a[ax]==0&&len-1>ac){
		ax++,ac++;
	}
	for(int i=ax;i<len;i++){
		cout<<a[i];
	}
	return 0;
}

P1478 陶陶摘苹果（升级版）

题目描述

又是一年秋季时，陶陶家的苹果树结了 n 个果子。陶陶又跑去摘苹果，这次他有一个 a 公分的椅子。当他手够不着时，他会站到椅子上再试试。

这次与 NOIp2005 普及组第一题不同的是：陶陶之前搬凳子，力气只剩下 s 了。当然，每次摘苹果时都要用一定的力气。陶陶想知道在 s<0 之前最多能摘到多少个苹果。

现在已知 n 个苹果到达地上的高度 xi，椅子的高度 a，陶陶手伸直的最大长度 b，陶陶所剩的力气 s，陶陶摘一个苹果需要的力气 yi，求陶陶最多能摘到多少个苹果。

输入格式

第 1 行：两个数苹果数 n，力气 s。

第 2 行：两个数椅子的高度 a，陶陶手伸直的最大长度 b。

第 3 行~第 3+n−1 行：每行两个数苹果高度 xi，摘这个苹果需要的力气 yi。

输出格式

只有一个整数，表示陶陶最多能摘到的苹果数。

输入输出样例

输入 #1复制

输出 #1复制

说明/提示

对于 100% 的数据，n≤5000, a≤50, b≤200, s≤1000, xi≤280, yi≤100。

实现代码

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

struct node{
	int gao,li;
}ax[5050];

bool cmp(node a,node b){
	return a.li<b.li;
}

int main(){
	int n,s,a,b,k=1;
	cin>>n>>s;
	cin>>a>>b;
	int high=a+b;
	for(int i=1;i<=n;i++){
		int x,y;
		cin>>x>>y;
		if(x<=high){
			ax[k].gao=x;
			ax[k].li=y;
			k++;
		}
	}
	int sum=0,cnt=0;
	sort(ax+1,ax+k,cmp);
	for(int i=1;i<k;i++){
		if(i==k-1){
			break;
		}
		else if(sum+ax[i].li<=s){
			cnt++;
			sum+=ax[i].li;
		}
		else break;
	}
	cout<<cnt;
	return 0;
}

P5019 [NOIP 2018 提高组] 铺设道路

题目背景

NOIP2018 提高组 D1T1

题目描述

春春是一名道路工程师，负责铺设一条长度为 n 的道路。

铺设道路的主要工作是填平下陷的地表。整段道路可以看作是 n 块连续的区域，一开始，第 i 块区域下陷的深度为 di 。

春春每天可以选择一段连续区间 [L,R] ，填充这段区间中的每块区域，让其下陷深度减少 1。在选择区间时，需要保证，区间内的每块区域在填充前下陷深度均不为 0 。

春春希望你能帮他设计一种方案，可以在最短的时间内将整段道路的下陷深度都变为 0 。

输入格式

输入文件包含两行，第一行包含一个整数 n，表示道路的长度。第二行包含 n 个整数，相邻两数间用一个空格隔开，第 i 个整数为 di 。

输出格式

输出文件仅包含一个整数，即最少需要多少天才能完成任务。

输入输出样例

输入 #1复制

6   
4 3 2 5 3 5

输出 #1复制

说明/提示

【样例解释】

一种可行的最佳方案是，依次选择： [1,6]、[1,6]、[1,2]、[1,1]、[4,6]、[4,4]、[4,4]、[6,6]、[6,6]。

【数据规模与约定】

对于 30% 的数据，1≤n≤10 ；
对于 70% 的数据，1≤n≤1000 ；
对于 100% 的数据，1≤n≤100000,0≤di≤10000 。

实现代码

#include<bits/stdc++.h>
using namespace std;
int n,a[100005];
long long ans=0;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)    
		cin>>a[i];
	for(int i=2;i<=n;i++)    
		if(a[i]>a[i-1]){
			ans+=a[i]-a[i-1];	
		} 
	cout<<ans+a[1];
	return 0;
}

P1208 [USACO1.3] 混合牛奶 Mixing Milk

题目描述

由于乳制品产业利润很低，所以降低原材料（牛奶）价格就变得十分重要。帮助 Marry 乳业找到最优的牛奶采购方案。

Marry 乳业从一些奶农手中采购牛奶，并且每一位奶农为乳制品加工企业提供的价格可能相同。此外，就像每头奶牛每天只能挤出固定数量的奶，每位奶农每天能提供的牛奶数量是一定的。每天 Marry 乳业可以从奶农手中采购到小于或者等于奶农最大产量的整数数量的牛奶。

给出 Marry 乳业每天对牛奶的需求量，还有每位奶农提供的牛奶单价和产量。计算采购足够数量的牛奶所需的最小花费。

注：每天所有奶农的总产量不少于 Marry 乳业的需求量。

输入格式

第一行二个整数 n,m，表示需要牛奶的总量，和提供牛奶的农民个数。

接下来 m 行，每行两个整数 pi,ai，表示第 i 个农民牛奶的单价，和农民 i 一天最多能卖出的牛奶量。

输出格式

单独的一行包含单独的一个整数，表示 Marry 的牛奶制造公司拿到所需的牛奶所要的最小费用。

输入输出样例

输入 #1复制

输出 #1复制

说明/提示

【数据范围】
对于 100% 的数据：
0≤n,ai≤2×106，0≤m≤5000，0≤pi≤1000。

题目翻译来自 NOCOW。

USACO Training Section 1.3

实现代码

#include<bits/stdc++.h>
using namespace std;
int n,m;

struct node{
	int price,volumn;
}a[2000500];

bool cmp(node a,node b){
	return a.price<b.price;
}

int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>a[i].price>>a[i].volumn;
	}
	sort(a+1,a+1+m,cmp);
	int sum=0,cnt=0;
	for(int i=1;i<=m;i++){
		if(sum+a[i].volumn<=n){
			sum+=a[i].volumn;
			cnt+=a[i].price*a[i].volumn;
		}
		else{
			cnt+=a[i].price*(n-sum);
			break;
		}
	}
	cout<<cnt;
	return 0;
}