贪心Tag Archive

【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 + 100和dish[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