【19HDU多校】Rikka with Coin,贪心

传送门

题意是说有面值10 20 50 100的钱,有n个价格给定的菜,要求用最少的硬币数量,使得所有n个菜品的价格都能被凑出来。

贪心:直观想法是先用大的面值,依次用小的面值。

这样的话可以发现10, 20, 20, 50四个面值能凑出所有100以内的价格。

但是有个例外:90 110 这样的数据,如果按照上面的贪法是100 50 20 20 10五个硬币,实际上只需要50 20 20 20四个硬币就可以拼出来。

所以进一步发现用10 20 20 20 50五个硬币可以包含所有最优方案。两个10肯定能用一个20代替,四个20肯定能用一个50 20 10代替。

所以做一个10 20 20 20 50的子集生成。然后暴力判断dish[i] % 100 + 100dish[i] % 100在某个组合的子集生成里有没有。(有先后顺序,第一个如果有了第二个就不用判断。因为既然零钱数量是固定的,那么100圆的越少约好)如果有,100圆的数量就分别是(dish[i] - (dish[i] % 100 + 100)/ 100) ,和dish[i] / 100

对于100圆判断是个重要细节。
比如1000 90 110这样的数据,1000其中的100圆可以用零钱拼出来,所以100圆个数只有9个。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[5] = {10, 20, 20, 20, 
Read the rest

【19牛客多校9_J】Symmetrical Painting【另类扫描线】

传送门

题意是说给n<=3e5条宽度为1的线段,长度不定。

要求一个对称轴,使得将图按照对称轴处理以后剩下的线段最多。

首先猜到的就是对称轴必定出现在某个线段的正中央。但是枚举对称轴以后需要用数据结构维护两边的长度。

有一种离线的做法,更为简单。

  1. 预处理出每条线的 下边线(l)、中线(l+r1)、上边线(r)。
  2. 对于这些预处理出的线,仅仅记录一个y坐标,按照坐标从小到大排序。

  3. 枚举这些线当作对称轴,从下往上做扫描线。线性讨论当前这条线和上一条线之间的线段产生的贡献。也就是当前线为对称轴,上一条线为下半段。按照扫描线一层一层的计算面积贡献。

  4. 在某个线段遇到中线之前,他的面积贡献都是存在的。因为他按照当前扫描线往上翻折,扫描线下方的面积肯定小 于上方,所以贡献是下方面积的两倍 ,于是下边界的贡献flag = 1。

  5. 当扫描线遇到中线的时候,肯定是之前某个线段的中线,此时这条线段在扫描线下方的面积大于等于上方面积,同时这条线段已经达到最大的面积贡献,当扫描线再往上走的时候会减少贡献,每当中线网上移动距离 k 的时候,这条线段就应该减去 2k 的面积贡献。当遇到上边界的时候负贡献消失,变成 0 贡献。于是中线的贡献flag = -2,上边界的flag = 1。

  6. 所以用变量cnt对当前层做出贡献的线段条数,面积和sum每次都+=cnt*(i-last)。然后cnt+=当前层数的贡献。因为兑成轴的只可能产生0.5这种小数,于是为了代码方便,把坐标都扩大两倍,同时计算面积的时候不用乘2。


其实最核心的点就是每当对称轴向上移动k距离的时候,整条线就应该缩短2k的距离,这样才能保证图形是对称的。


#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const int maxn = 3e5 + 233;
int n;
vector<pii> a;
int main()
{
    int n; cin >> n;
    for(int i = 1; i <= n; i++)
    {
        ll l, r;
        cin >> l >> r;
        a.push_back({l * 
Read the rest

【二分-贪心】问题集合

二分这类问题 通常需要猜结论乱搞,解决此类问题的方法,就是见多识广

Q1

题意是说一个船会随风飘动,风的方向有周期。船每天也可以选择往一个方向自由航行,效果和风叠加,类似矢量。问最少多少天能到目的地。

做法是二分天数。天数定了,船如果不动,终点就是定了的。再此基础上船还可以走 天数 这么多步。如果和目的地的距离小于这个步数就缩减天数。

单调性:对于mid天,如果能达到,那么大于mid天也肯定能达到,因为多出的天数船可以想办法每天抵消风的影响呆在原地。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 233;
int n, dirx[maxn], diry[maxn], desx, desy,inix,iniy;
string s;
int main()
{
    cin >> inix >> iniy >> desx >> desy;
    if(inix == desx && iniy == desy)
    {cout<<0;return 0;}
    cin >> n >> s;
    for(int i = 1; i <= n; i++ )
    {
        if(s[i - 1] == 'U') diry[i] = 1;
        if(s[i - 1] == 'D') 
Read the rest

【数学-贪心-末状态已知】问题集合

  • 蓝书 P4 分金币

https://vjudge.net/problem/UVA-11300

关于本题的“想一想为什么”:因为非齐次方程组的系数行列式为0,所以方程的解不唯一,所以最后一个方程没有贡献。

末态相同的题目,可以往方程组方向去想。最后可以往坐标的距离方面去靠。

  • 蓝书 P7 雕塑

本题第一个设想“有一个雕塑不会动”的证明:

设开始每个墓碑相差A,移动后每个墓碑相差M,M可以不相同,因为有加进来的雕塑。设Xi为向下一个雕塑移动的距离。则有

[latex][/latex]A-X_1+X_2=M =X_2=X_1-(A-M)

A-X_2+X_3=M =X_3=X_1-2(A-M)

A-X_n+X_1=M =X_n=X_1-n(A-M)

 

同样可以变成X1到各个数字的距离最小的问题,即可知道X1在中位数的时候此时的距离为0。所以必然有一个雕塑它移动的距离为0。但不可用此方法求解答案,因为M仅仅是假设存在一个M使其满足末态,由于加入的雕塑不知道位置所以M无法确定。应采用贪心的方法求解… Read the rest

【优先队列-贪心】问题集合

  • 中间商优化

http://codeforces.com/problemset/problem/867/E

一个长度为N的序列,代表每天股票的价格,每天只能执行 买/卖/无动作 三种操作。问如何才能赚得最多。

维护一个优先队列,队首存当前最小的价格,见到比最小的价格高的就先卖掉,并且把低价股票的价格变成当前价格,更低的就进队。如果以后遇到更高的可以和交易过的股票交易,也可以和没交易过的股票交易,它们赚的钱是一样的。。经过xyjj的指点知道了这类题的做法叫中间商优化,先找到更高的卖了提升价格,以后可以继续交易。

#include<iostream>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<vector> 
#include<utility>
using namespace std;
typedef long long ll;
priority_queue<ll,vector<ll>,greater<ll> > b;

ll n,t;
ll ans=0;
int main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&t);
		b.push(t);
		if(b.top()<t)
		{
			ans+=t-b.top();
			b.pop();
			b.push(t);
		}
	}
	printf("%lld",ans);
}

 … Read the rest