10/10 每周总结报告 3

本周主要刷了贪心专题,以下选择一些经典题分析。
3Allowance G

#include
#include
const int N=100001+5;
using namespace std;
struct node {
    int buy,num;
}aa[N];

int n,c,ans;
bool cmp(node a1,node a2)
{ return a1.buy>a2.buy; }
int main()
{
    cin>>n>>c;
    for(int i=1;i<=n;i++)
    {
       cin>>aa[i].buy>>aa[i].num;
    }

    sort(aa+1,aa+n+1,cmp);

    int now=1;
    while (aa[now].buy>=c) {
        ans+=aa[now].num;
        now++;
    }
    while (1) {
        int ka=c;
        for(int i=now;i<=n;i++)
        {while (ka>=aa[i].buy&&aa[i].num&&ka>0) {
                ka-=aa[i].buy;
                aa[i].num--;
            }
        }
        if(ka>0) for(int i=n;i>=now;i--) {
            if(aa[i].buy>=ka&&aa[i].num) {
                aa[i].num--;
                ka-=aa[i].buy;
                break ;
            }
        }
        if(ka>0) break ;
        ans++;
    }

    cout< 
题意:每周给大于一定的钱,要求最多能给多少周钱。贪心思路是首先将大于每周给的钱的一周一周先给完，如果只剩下小于最少给的钱，那么判断，最有可能的组合，即可。主要实现代码是
 
for(int i=now;i<=n;i++)
        {while (ka>=aa[i].buy&&aa[i].num&&ka>0) {
                ka-=aa[i].buy;
                aa[i].num--;
            }
        }
 
但是还需要判断是否到达临界条件，是否能够刚好给够钱，如果不能那么直接用剩下的最大的一个先给上。
 
P6877 [JOI 2020 Final] 長いだけのネクタイ
 
#include
#include
const int N=200000+5;
using namespace std;

struct node
{
	int data,t;
}a[N];;
int n,b[N],W[N],A[N],B[N];
bool cmp(node x,node y){
return x.data>n;
	for (int i=1;i<=n+1;++i)
		{cin>>a[i].data;a[i].t=i;}
	for (int i=1;i<=n;++i)
		cin>>b[i];
	sort(a+1,a+n+2,cmp);
	sort(b+1,b+1+n);
	//for (int i=1;i<=n;++i)
      //  cout<
	for (int i=1;i<=n;++i)
		A[i]=max(A[i-1],max(a[i].data-b[i],0));
	for (int i=n;i;--i)
		B[i]=max(B[i+1],max(a[i+1].data-b[i],0));
	for (int i=1;i<=n+1;++i)
		W[a[i].t]=i;
	for (int i=1;i<=n+1;++i)cout< 
此题题意:老板选出一个领带后，要求最小的领带长度差，所有的员工最大的领带长度差最小，依次打印出老板选出领带后，最小领带差.
 题目很清晰，很显然可以想到，可以先第一次领带和第二次领带长度，从小到大排序，然后依次减对应的领带便可以得到最小的领带长度，但是真的是这样吗？做到时候我也以为这是一道十分简单的题，但是提交答案发现，有一半的数据过不了，说明有情况没有讨论到，想了很久，看到一个题解十分清晰，也就是和我这个代码类似，首先将两个数组从小到大排序,假如ai与bj结合(i>j)而bi和aj对应,那么满足ai>aj;bi>bj;并且可以推出ai-bi>aj-bj>aj-bi,max(ai-bj,aj-bi)=ai-bj>ai-bi.
 总结：感觉省选的题都好难，好多思想都很难想到，唉。