洛谷刷题8

贪心策略的讲解和用法

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。

贪心算法不是对所有问题都能得到体最优解，关键是整贪心策略的选择

贪心算法一般按如下步骤进行：

①建立数学模型来描述问题。

②把求解的问题分成若干个子问题。

③对每个子问题求解，得到子问题的局部最优解。

④把子问题的解局部最优解合成原来解问题的一个解。

【深基12.例1】部分背包问题

题目描述

阿里巴巴走进了装满宝藏的藏宝洞。藏宝洞里面有 $N(N \le 100)$ 堆金币，第 $i$ 堆金币的总重量和总价值分别是 $m_i,v_i(1\le m_i,v_i \le 100)$。阿里巴巴有一个承重量为 $T(T \le 1000)$ 的背包，但并不一定有办法将全部的金币都装进去。他想装走尽可能多价值的金币。所有金币都可以随意分割，分割完的金币重量价值比（也就是单位价格）不变。请问阿里巴巴最多可以拿走多少价值的金币？

输入格式

第一行两个整数 $N,T$。

接下来 $N$ 行，每行两个整数 $m_i,v_i$。

输出格式

一个实数表示答案，输出两位小数

样例 #1

样例输入 #1

样例输出 #1

240.00

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
struct coin
{
	int m, v;

}a[110];

bool  cmp(coin x, coin y)
{
	return x.v * y.m > x.m * y.v;



}
int main()
{
	int n, c;
	cin >> n >> c;
	float ans = 0;
	int i;
	for ( i = 0; i < n; i++)
	{
		cin >> a[i].m >> a[i].v;
	}

	sort(a, a + n, cmp);
	for ( i = 0; i < n; i++)
	{
		if (c<a[i].m)
		{
			break;
		}
		c -= a[i].m;
		ans += a[i].v;


	}

	if (i<n)
	{
		ans += 1.0 * c / a[i].m * a[i].v;
	}
	printf("%.2f", ans);

}
//贪心每次拿走性价比最高的

排队接水

题目描述

有 $n$ 个人在一个水龙头前排队接水，假如每个人接水的时间为 $T_i$，请编程找出这 $n$ 个人排队的一种顺序，使得 $n$ 个人的平均等待时间最小。

输入格式

第一行为一个整数 $n$。

第二行 $n$ 个整数，第 $i$ 个整数 $T_i$ 表示第 $i$ 个人的接水时间 $T_i$。

输出格式

输出文件有两行，第一行为一种平均时间最短的排队顺序；第二行为这种排列方案下的平均等待时间（输出结果精确到小数点后两位）。

样例 #1

样例输入 #1

1 2	10 56 12 1 99 1000 234 33 55 99 812

样例输出 #1

1 2	3 2 7 8 1 4 9 6 10 5 291.90

提示

$1\le n \leq 1000$，$1\le t_i \leq 10^6$，不保证 $t_i$ 不重复。

#include <iostream>
#include<climits>
#include<iomanip>
using namespace std;
long arr[2000] = { 0 };
int main()
{
	//n个人的排队时间输入
	int N;
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}

	//复制一次数组，便于操作；
	long arr1[2000] = { 0 };
	for (int i = 0; i < N; i++)
	{
		arr1[i] = arr[i];
	}

	//先查找，用数组记录下标后再排序；
	int x = 0; int arr2[2000] = { 0 }; int min = 1;
	int n;
	//检验是否查找完毕；
	while (min)
	{
		min = 0;//找是否有非负项，找完了就结束循环
		for (int i = 0; i < N; i++)
		{
			if (arr[i] > 0)
			{
				min = arr[i];
				n = i;//确保有下标录入；
				break;
			}

		}
		//查找并录入最小值的下标,剔出已录入的（赋一个负值，改条件）

		if (min > 0)
		{
			for (int i = 0; i < N; i++)
			{
				if (arr[i] < min && arr[i] > 0)
				{
					min = arr[i];
					n = i;
				}
			}
			arr2[x] = n + 1;
			arr[n] = -1;
			x++;
		}

	}
	//输出查找的最小值的排序；
	for (int i = 0; i <= x - 1; i++)
		cout << arr2[i] << " ";
	cout << endl;
	//对复制的数组arr1排序(冒泡排序）
	for (int i = 0; i < N - 1; i++)
	{
		for (int j = 0; j < N - i - 1; j++)
		{
			if (arr1[j + 1] < arr1[j])
			{
				int temp = arr1[j];
				arr1[j] = arr1[j + 1];
				arr1[j + 1] = temp;
			}
		}
	}
	//计算平均时间
	double t = 0;
	for (int i = 1; i <= N - 1; i++)
	{
		for (int i1 = 0; i1 < i; i1++)
		{
			t += arr1[i1];
		}
	}
	
	double t0 = t / N;
	printf("%.2f", t0);
}
//自己写的，写的很抽象

//题解写的，很好理解
//先结构体排序，接着进行运算即可
#include"iostream"
#include"cstdio"
#include"algorithm"//为了用sort快排
using namespace std;
struct a  
{
 int b,num;//定义结构体a      
};
bool cmp(a x,a y)//定义“小于”运算符
{
 return x.b<y.b;    
}
int main()
{
 struct a a[1010];//定义结构体数组
 int n,i,j;
 double time=0;
 cin>>n;    
 for(i=1;i<=n;i++)   
  {
   cin>>a[i].b;
   a[i].num=i;//序号存起来              
  } 
 sort(a+1,a+n+1,cmp);//排序
  for(i=1;i<=n;i++)
  {
   cout<<a[i].num<<" "; //先把简单的做了，输入由小到大的编号
  }
  cout<<endl;//要换行
  for(j=n-1;j>=1;j--) //等待人数的计数器，由n-1开始
  {
   i=n-j;//这是个规律，当前最少时间的人序号和要等待的人数之和=n
   time+=a[i].b*j; //累加                  
  }
 printf("%.2lf",time/n);//算平均，保留两位小数
  return 0; 
}

凌乱的yyy / 线段覆盖

题目背景

快 noip 了，yyy 很紧张！

题目描述

现在各大 oj 上有 $n$ 个比赛，每个比赛的开始、结束的时间点是知道的。

yyy 认为，参加越多的比赛，noip 就能考的越好（假的）。

所以，他想知道他最多能参加几个比赛。

由于 yyy 是蒟蒻，如果要参加一个比赛必须善始善终，而且不能同时参加 $2$ 个及以上的比赛。

输入格式

第一行是一个整数 $n$，接下来 $n$ 行每行是 $2$ 个整数 $a_{i},b_{i}\ (a_{i}<b_{i})$，表示比赛开始、结束的时间。

输出格式

一个整数最多参加的比赛数目。

样例 #1

样例输入 #1

样例输出 #1

提示

对于 $20\%$ 的数据，$n \le 10$；
对于 $50\%$ 的数据，$n \le 10^3$；
对于 $70\%$ 的数据，$n \le 10^{5}$；
对于 $100\%$ 的数据，$1\le n \le 10^{6}$，$0 \le a_{i} < b_{i} \le 10^6$。

#include<iostream>
#include<algorithm>
#include<string>
#include<math.h>
#include<cmath>
using namespace std;
struct contest
{
	int l;
	int r;

}con[100000000];
bool cmp(contest x, contest y)
{
	return x.r <= y.r;




}
int main()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> con[i].l >> con[i].r;


	}
	sort(con, con + n,cmp);

	int ans = 0;
	int finish = 0;
	for (int i = 0; i < n; i++)
	{
		if (finish<=con[i].l)
		{
			ans++;
			finish = con[i].r;


		}


	}
	cout << ans;


	return 0;
}

[NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G

题目描述

在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。

每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过 $n-1$ 次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。

因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为 $1$ ，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。

例如有 $3$ 种果子，数目依次为 $1$ ， $2$ ， $9$ 。可以先将 $1$ 、 $2$ 堆合并，新堆数目为 $3$ ，耗费体力为 $3$ 。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为 $12$ ，耗费体力为 $12$ 。所以多多总共耗费体力 $=3+12=15$ 。可以证明 $15$ 为最小的体力耗费值。

输入格式

共两行。
第一行是一个整数 $n(1\leq n\leq 10000)$ ，表示果子的种类数。

第二行包含 $n$ 个整数，用空格分隔，第 $i$ 个整数 $a_i(1\leq a_i\leq 20000)$ 是第 $i$ 种果子的数目。

输出格式

一个整数，也就是最小的体力耗费值。输入数据保证这个值小于 $2^{31}$ 。

样例 #1

样例输入 #1

1
2

3 
1 2 9

样例输出 #1

提示

对于 $30\%$ 的数据，保证有 $n \le 1000$：

对于 $50\%$ 的数据，保证有 $n \le 5000$；

对于全部的数据，保证有 $n \le 10000$。

//单调队列
#include<bits/stdc++.h>
using namespace std;
const int N=1e7;
#define rep(i,a,n) for(int i=a;i<=n;i++)
priority_queue <int,vector<int>,greater<int> >q;
int main()
{
int n,x,y;
int ans=0;
int cost;
cin>>n;
rep(i,1,n)
{
    cin>>x;
    q.push(x);
}
while(q.size()>1)
{
    x=q.top();
q.pop();
    y=q.top();
q.pop();
cost =x+y;
q.push(cost);
ans+=cost;
}
cout<<ans;


}

小A的糖果

题目描述

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

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

输入格式

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

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

输出格式

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

样例 #1

样例输入 #1

1
2

3 3
2 2 2

样例输出 #1

样例 #2

样例输入 #2

1 2	6 1 1 6 1 2 0 4

样例输出 #2

样例 #3

样例输入 #3

1 2	5 9 3 1 4 1 5

样例输出 #3

提示

样例输入输出 1 解释

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

样例输入输出 2 解释

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

数据规模与约定

对于 $30\%$ 的数据，保证 $n \leq 20$，$a_i, x \leq 100$。
对于 $70\%$ 的数据，保证 $n \leq 10^3$，$a_i, x \leq 10^5$。
对于 $100\%$ 的数据，保证 $2 \leq n \leq 10^5$，$0 \leq a_i, x \leq 10^9$。

#include<iostream>
#include<algorithm>
using namespace std;

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

# 删数问题

题目描述

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

输入格式

输入两行正整数。

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

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

输出格式

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

样例 #1

样例输入 #1

1
2

175438 
4

样例输出 #1

#include<iostream>
#include<string>
using namespace std;
int b[10000];
int main()
{
	string st;//字符串
	cin >> st;
	int n;//删除的次数
	cin >> n;
	int len = st.length();
	for (int i = 0; i < len; i++)
	{
		b[i] = st[i] - '0';

	}
	for (int k = 1; k<=n; k++)
	{
		//遍历n次，因为要删除n个
		for (int i = 0; i < len; i++)
		{
			if (b[i]>b[i+1])
			{
				for (int j = i; j < len; j++)
				{
					b[j] = b[j + 1];//删除操作
				
					
				}
				len--;
				break;
			}
		}
	}//删除操作完成
	//去前导0操作来袭
	int i = 0;
	int l = 0;
	while (b[i]==0&&l<len-1)
	{
		l++;
		i++;
	}
	for (int i = l; i < len; i++)
	{
		cout << b[i];
	}
	return 0;
}

陶陶摘苹果（升级版）

题目描述

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

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

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

输入格式

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

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

第 $3$ 行~第 $3+n-1$ 行：每行两个数苹果高度 $x_i$，摘这个苹果需要的力气 $y_i$。

输出格式

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

样例 #1

样例输入 #1

样例输出 #1

提示

对于 $100\%$ 的数据，$n\leq 5000$, $a\leq 50$, $b\leq 200$, $s\leq 1000$, $x_i\leq 280$, $y_i\leq 100$。

#include<iostream>
#include<algorithm>
using namespace std;
int n, s, a, b;
struct app {
	int x;
	int y;
}c[10500];
int num;
bool cmp(app j, app k) {

	return j.y < k.y;
    //先摘取最小的
}
int main() {
	cin >> n >> s;
	cin >> a >> b;
	for (int i = 1; i <= n; i++) {
		cin >> c[i].x >> c[i].y;
	}
	sort(c + 1, c + 1 + n, cmp);
	for (int i = 1; i<=n; i++) {
		if (c[i].x <= a + b) {
			if (s-c[i].y>=0)
			{
				s -= c[i].y;
				num++;
			}
		}
	}
	cout << num;
	return 0;
}

[NOIP2018 提高组] 铺设道路

题目背景

NOIP2018 提高组 D1T1

题目描述

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

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

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

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

输入格式

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

输出格式

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

样例 #1

样例输入 #1

1 2	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 ≤ d_i ≤ 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;
}

[USACO1.3] 混合牛奶 Mixing Milk

题目描述

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

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

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

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

输入格式

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

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

输出格式

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

样例 #1

样例输入 #1

样例输出 #1

提示

【数据范围】
对于 $100\%$ 的数据：
$0 \le n,a_i \le 2 \times 10^6$，$0\le m \le 5000$，$0 \le p_i \le 1000$

题目翻译来自 NOCOW。

USACO Training Section 1.3

//找价格最少即可
#include<iostream>
#include<algorithm>

#include<string>
using namespace std;

struct niunai
{
	int jiage;
	int shuliang;
}a[10000];
bool cmp(niunai x, niunai y)
{

	return x.jiage < y.jiage;
}
int main()
{

	int n, m;
	int sum = 0;

	cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
		cin >> a[i].jiage >> a[i].shuliang;
	}
	sort(a, a + m, cmp);
	int i;
	for ( i = 0; i < m; i++)
	{
		if (n-a[i].shuliang>=0)
		{
			sum += a[i].jiage * a[i].shuliang;
			n -= a[i].shuliang;
		}
		else
		{
			break;
		}


	}


	sum += a[i].jiage * n;

	cout << sum;

}

[NOIP2007 普及组] 纪念品分组

题目背景

NOIP2007 普及组 T2

题目描述

元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得的纪念品价值相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪念品，并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品，乐乐希望分组的数目最少。

你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。

输入格式

共 $n+2$ 行：

第一行包括一个整数 $w$，为每组纪念品价格之和的上限。

第二行为一个整数 $n$，表示购来的纪念品的总件数 $G$。

第 $3\sim n+2$ 行每行包含一个正整数 $P_i$ 表示所对应纪念品的价格。

输出格式

一个整数，即最少的分组数目。

样例 #1

样例输入 #1

样例输出 #1

提示

$50\%$ 的数据满足：$1\le n\le15$。

$100\%$ 的数据满足：$1\le n\le3\times10^4$，$80\le w\le200$，$5 \le P_i \le w$。

//找两端最大的
#include<iostream>
#include<algorithm>
using namespace std;
int a[100000000];
int main()
{
	int w;
	cin >> w;
	int n;
	cin >> n;
	
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];

	}
	sort(a + 1, a + n + 1);

	int l = 1;
	int r = n;
	int sum = 0;
	while (l<=r)
	{
		if (a[l]+a[r]<=w)
		{
			l++, r--;
			sum += 1;
		}
		else
		{
			r--;
			sum++;
		}


	}


	cout << sum;

	return 0;
}

跳跳！

题目描述

你是一只小跳蛙，你特别擅长在各种地方跳来跳去。

这一天，你和朋友小 F 一起出去玩耍的时候，遇到了一堆高矮不同的石头，其中第 $i$ 块的石头高度为 $h_i$，地面的高度是 $h_0 = 0$。你估计着，从第 $i$ 块石头跳到第 $j$ 块石头上耗费的体力值为 $(h_i - h_j) ^ 2$，从地面跳到第 $i$ 块石头耗费的体力值是 $(h_i) ^ 2$。

为了给小 F 展现你超级跳的本领，你决定跳到每个石头上各一次，并最终停在任意一块石头上，并且小跳蛙想耗费尽可能多的体力值。

当然，你只是一只小跳蛙，你只会跳，不知道怎么跳才能让本领更充分地展现。

不过你有救啦！小 F 给你递来了一个写着 AK 的电脑，你可以使用计算机程序帮你解决这个问题，万能的计算机会告诉你怎么跳。

那就请你——会写代码的小跳蛙——写下这个程序，为你 NOIp AK 踏出坚实的一步吧！

输入格式

输入一行一个正整数 $n$，表示石头个数。

输入第二行 $n$ 个正整数，表示第 $i$ 块石头的高度 $h_i$。

输出格式

输出一行一个正整数，表示你可以耗费的体力值的最大值。

样例 #1

样例输入 #1

1
2

2
2 1

样例输出 #1

样例 #2

样例输入 #2

1
2

3
6 3 5

样例输出 #2

提示

样例解释

两个样例按照输入给定的顺序依次跳上去就可以得到最优方案之一。

数据范围

对于 $1 \leq i \leq n$，有 $0 < h_i \leq 10 ^ 4$，且保证 $h_i$ 互不相同。

对于 $10\%$ 的数据，$n \leq 3$；

对于 $20\%$ 的数据，$n \leq 10$；

对于 $50\%$ 的数据，$n \leq 20$；

对于 $80\%$ 的数据，$n \leq 50$；

对于 $100\%$ 的数据，$n \leq 300$。

//差距最大反复横跳
    #include<iostream>
using namespace std;
int a[100000];
int b[100000] = { 0 };
int main()
{
	int n;
	cin >> n;
	int now = 0;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];


	}
	long long sum = 0;
	int cmax = 0;
	int t;
	int j;
	int z;
	for (int i = 0; i < n; i++)
	{
		for ( j = 0; j < n; j++)
		{
			if ((abs(a[j] - now)) * (abs(a[j] - now))>cmax&&!b[j])
			{
				cmax = abs(a[j] - now) * abs(a[j] - now);
				t = a[j];
				z = j;


			}
		
		}
		sum += cmax;
		cmax = 0;
		now = t;
		b[z] = 1;



	}
	cout << sum;

	return 0;
}

[AHOI2018初中组] 分组

题目描述

小可可的学校信息组总共有 $n$ 个队员，每个人都有一个实力值 $a_i$。现在，一年一度的编程大赛就要到了，小可可的学校获得了若干个参赛名额，教练决定把学校信息组的 $n$ 个队员分成若干个小组去参加这场比赛。

但是每个队员都不会愿意与实力跟自己过于悬殊的队员组队，于是要求分成的每个小组的队员实力值连续，同时，一个队不需要两个实力相同的选手。举个例子：$[1, 2, 3, 4, 5]$ 是合法的分组方案，因为实力值连续；$[1, 2, 3, 5]$ 不是合法的分组方案，因为实力值不连续；$[0, 1, 1, 2]$ 同样不是合法的分组方案，因为出现了两个实力值为 $1$ 的选手。

如果有小组内人数太少，就会因为时间不够而无法获得高分，于是小可可想让你给出一个合法的分组方案，满足所有人都恰好分到一个小组，使得人数最少的组人数最多，输出人数最少的组人数的最大值。

注意：实力值可能是负数，分组的数量没有限制。

输入格式

输入有两行：

第一行一个正整数 $n$，表示队员数量。
第二行有 $n$ 个整数，第 $i$ 个整数 $a_i$ 表示第 $i$ 个队员的实力。

输出格式

输出一行，包括一个正整数，表示人数最少的组的人数最大值。

样例 #1

样例输入 #1

1 2	7 4 5 2 3 -4 -3 -5

样例输出 #1

提示

【样例解释】分为 $2$ 组，一组的队员实力值是 $\{4, 5, 2, 3\}$，一组是 $\{-4, -3, -5\}$，其中最小的组人数为 $3$，可以发现没有比 $3$ 更优的分法了。

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
const int N=1e5+40;
int f[N],n,ans=1e9,siz[N],top,q[N];
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++) cin>>f[i];
	sort(f+1,f+n+1);
	for(int i=1;i<=n;i++){
		int pos=lower_bound(q+1,q+top+1,f[i])-q; 
        //查询大于或等于他的
		while(q[pos+1]==f[i]&&pos<top) pos++;
        //查询最后一个等于他的
		if(pos>top||q[pos]!=f[i]) siz[++top]=1,q[top]=f[i]+1;
        //不等于再开，并记录下一个要进来的（如果有）
		else siz[pos]++,q[pos]++;
        //有就加，并更新待会要进来的值
	}
	for(int i=1;i<=top;i++) ans=min(ans,siz[i]);  
cout<<ans;
}

[NOIP2012 提高组] 国王游戏

题目描述

恰逢 H 国国庆，国王邀请 $n$ 位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。然后，让这 $n$ 位大臣排成一排，国王站在队伍的最前面。排好队后，所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是：排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。

国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能的少。注意，国王的位置始终在队伍的最前面。

输入格式

第一行包含一个整数 $n$，表示大臣的人数。

第二行包含两个整数 $a$ 和 $b$，之间用一个空格隔开，分别表示国王左手和右手上的整数。

接下来 $n$ 行，每行包含两个整数 $a$ 和 $b$，之间用一个空格隔开，分别表示每个大臣左手和右手上的整数。

输出格式

一个整数，表示重新排列后的队伍中获奖赏最多的大臣所获得的金币数。

样例 #1

样例输入 #1

样例输出 #1

提示

【输入输出样例说明】

按 $1$、$2$、$3$ 这样排列队伍，获得奖赏最多的大臣所获得金币数为 $2$；

按 $1$、$3$、$2$ 这样排列队伍，获得奖赏最多的大臣所获得金币数为 $2$；

按 $2$、$1$、$3$ 这样排列队伍，获得奖赏最多的大臣所获得金币数为 $2$；

按$ 2$、$3$、$1 $这样排列队伍，获得奖赏最多的大臣所获得金币数为 $9$；

按 $3$、$1$、$2 $这样排列队伍，获得奖赏最多的大臣所获得金币数为 $2$；

按$ 3$、$2$、$1$ 这样排列队伍，获得奖赏最多的大臣所获得金币数为 $9$。

因此，奖赏最多的大臣最少获得 $2$ 个金币，答案输出 $2$。

【数据范围】

对于 $20\%$ 的数据，有 $1≤ n≤ 10,0 < a,b < 8$；

对于 $40\%$ 的数据，有$ 1≤ n≤20,0 < a,b < 8$；

对于 $60\%$ 的数据，有 $1≤ n≤100$；

对于 $60\%$ 的数据，保证答案不超过 $10^9$；

对于 $100\%$ 的数据，有 $1 ≤ n ≤1,000,0 < a,b < 10000$。

NOIP 2012 提高组第一天第二题

//本题的难点是排序要怎么排序？
//不妨想，相邻两个人，如果后者
a2/b1 vs a1/b2
要比较小的话
    实际上就是要让乘积较小排前面，局部贪心
整体贪心：相邻两个不会影响后面，因此不断推，就是整体。
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1010;

struct bign{
    const int BASE=1e4;
    int a[MAXN<<2],len;
    bign(int len=0){
        this->len=len;
    }
    bign operator=(int rhs){
        len=0;
        if(rhs==0){
            len=1;
            return *this;
        }
        while(rhs){
            a[++len]=rhs%BASE;
            rhs/=BASE;
        }
        return *this;
    }
    bign operator=(const bign rhs){
        memcpy(a,rhs.a,sizeof(rhs.a));
        len=rhs.len;
        return *this;
    }
    void operator*=(const int rhs){
        for(int i=1;i<=len;i++)
            a[i]*=rhs;
        for(int i=1;i<=len;i++){
            a[i+1]+=a[i]/BASE;
            a[i]%=BASE;
            if(i+1>len&&a[i+1])
                len++;
        }
        while(len&&a[len]==0)
            len--;
    }
    bign operator/(const int rhs){
        bign c;c=*this;
        while(c.len&&c.a[c.len]==0)
            c.len--;
        for(int i=c.len;i;i--){
            c.a[i-1]+=(c.a[i]%rhs)*BASE;
            c.a[i]/=rhs;
        }
        while(c.len&&c.a[c.len]==0)
            c.len--;
        return c;
    }
    void print(){
        while(len&&a[len]==0)
            len--;
        if(len==0){
            putchar('0');
            return;
        }
        printf("%d",a[len]);
        for(int i=len-1;i;i--)
            printf("%04d",a[i]);
    }
    bool operator>(const bign &rhs)const{
        if(len!=rhs.len)
            return len>rhs.len;
        for(int i=len;i;i--)
            if(a[i]!=rhs.a[i])
                return a[i]>rhs.a[i];
        return 0;
    }
}mul,ans;
//高精模板

struct node{
    int a,b;
    bool operator<(const node &rhs)const{
        return a*b<rhs.a*rhs.b||(a*b==rhs.a*rhs.b&&a>rhs.a);
    }
}p[MAXN];
//排序

int main(){

    int n;
    cin>>n;
    for(int i=0;i<=n;i++)
   cin>>p[i].a>>p[i].b;
    sort(p+1,p+n+1);
    mul=p[0].a;
    for(int i=1;i<=n;i++){
        bign tmp=mul/p[i].b;
        if(tmp>ans)
            ans=tmp;
        mul*=p[i].a;
        //结果回收
    }
    ans.print();
}