这题经过面条老师的指导终于AC了,好不容易啊

这个题用贪心的方法,需要注意的是贪心策略的设计

面条老师的设计

对第二道菜排序第一个方案:在1~i中找最小的第一道,然后再按顺序填第二道菜
第二个方案,在i~n中找最小的一道菜,然后按顺序填第二道菜

我理解了,然后就有了这个始终懵掉的87分代码

#include<bits/stdc++.h>
using namespace std;
struct Dish
{
    int a , b ;
};
struct T
{
    int l , r ;
};
Dish d[ 500001 ] ;
long long sum[ 500001 ] ;
T mindish[ 500001 ] ;
int n ;
bool cmp( Dish t1 , Dish t2 )
{
    return t1.b < t2.b ;
}
int main()
{
    ios::sync_with_stdio( 0 ) ;
    cin.tie( 0 ) ;
    cin >> n ;
    for( int i = 1 ; i <= n ; i ++ ) cin >> d[ i ].a >> d[ i ].b ;
    sort( d + 1 , d + n + 1 , cmp ) ;
    for( int i = 1 ; i <= n ; i ++ ) sum[ i ] = sum[ i - 1 ] + d[ i ].b ;
    mindish[ 1 ].l = 1 , mindish[ n ].r = n ;
    for( int i = 2 ; i <= n ; i ++ )
    {
        if( d[ i ].a < d[ mindish[ i - 1 ].l ].a ) mindish[ i ].l = i ;
        else if( d[ i ].a == d[ mindish[ i - 1 ].l ].a and d[ i ].b > d[ mindish[ i - 1 ].l ].b ) mindish[ i ].l = i ; 
        else mindish[ i ].l = mindish[ i - 1 ].l ;
    }
    for( int i = n - 1 ; i >= 1 ; i -- )
    {
        if( d[ i ].a < d[ mindish[ i + 1 ].r ].a ) mindish[ i ].r = i ;
        else if( d[ i ].a == d[ mindish[ i + 1 ].r ].a and d[ i ].b > d[ mindish[ i + 1 ].r ].b ) mindish[ i ].r = i ;
        else mindish[ i ].r = mindish[ i + 1 ].r ;
    }
    for( int i = 1 ; i <= n ; i ++ )
    {
        long long t1 = sum[ i ] - d[ mindish[ i ].l ].b + d[ mindish[ i ].l ].a ;
        long long t2 = 
        sum[ i - 1 ] + d[ mindish[ i ].r ].a ;
        cout << min( t1 , t2 ) << "\n" ;
    }
    return 0;
}

然后老师换了一种想法跟我说(算是吧)

对于上面提到的第一个方案比较方法变为了
s[ i ] = min( s3[ i - 1 ] , s[ i ].a - s[ i ].b ) ;

核心代码替换掉并且因为我上面的代码前缀和数组记录的是下标的缘故可能比较难以理解

就把前缀和数组储存下标改为直接存储数字

然后 成功AC

就有了下面的100分代码

#include<bits/stdc++.h>
using namespace std;
struct Dish
{
    int a , b ;
};
struct T
{
    int l , r ;
};
Dish d[ 500001 ] ;
long long sum[ 500001 ] ;
T mindish[ 500001 ] ;
int n ;
bool cmp( Dish t1 , Dish t2 )
{
    return t1.b < t2.b ;
}
int main()
{
    ios::sync_with_stdio( 0 ) ;
    cin.tie( 0 ) ;
    cin >> n ;
    for( int i = 1 ; i <= n ; i ++ ) cin >> d[ i ].a >> d[ i ].b ;
    sort( d + 1 , d + n + 1 , cmp ) ;
    for( int i = 1 ; i <= n ; i ++ ) sum[ i ] = sum[ i - 1 ] + d[ i ].b ;
    mindish[ 1 ].l = d[ 1 ].a - d[ 1 ].b , mindish[ n ].r = d[ n ].a ;
    for( int i = 2 ; i <= n ; i ++ )
    {
        mindish[ i ].l = min( mindish[ i - 1 ].l , d[ i ].a - d[ i ].b ) ;
    }
    for( int i = n - 1 ; i >= 1 ; i -- )
    {
        mindish[ i ].r = min( mindish[ i + 1 ].r , d[ i ].a ) ;
    }
    for( int i = 1 ; i <= n ; i ++ )
    {
        long long t1 = sum[ i ] + mindish[ i ].l ;
        long long t2 = sum[ i - 1 ] + mindish[ i ].r ;
        cout << min( t1 , t2 ) << "\n" ;
    }
    return 0;
}

emm顺便一提

楼下一个大佬不爱写题解了,所以我不要脸代写他的题解

点击这里膜拜大佬

大佬的AC Code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=500005;
int n,pos;
struct food
{
	int x,y;
	bool operator<(food w)const
	{
		return y<w.y;
	}
}a[N];
ll minx[N],minc;
ll ans;
inline int read()
{
	int x=0,f=1;char st=getchar();
	while(st<'0'||st>'9'){if(st=='-') f=-1;st=getchar();}
	while(st>='0'&&st<='9') x=x*10+st-'0',st=getchar();
	return x*f;
}
int main()
{
	n=read();
	for(int i=1;i<=n;i++)
	{
		a[i].x=read(),a[i].y=read();
	}
	sort(a+1,a+1+n);
	minx[n]=9999999999999;
	for(int i=n-1;i>=1;i--)
		minx[i]=min(minx[i+1],(ll)a[i+1].x);
	minc=9999999999999;
	for(int i=1;i<=n;i++)
	{
		minc=min(minc,(ll)a[i].x-a[i].y);
		ans+=a[i].y;
		printf("%lld\n",min(ans-a[i].y+minx[i],ans+minc));
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}

大佬带话(bushi)

你用我的代码发个100pts题解吧我懒得写了（记得写咬打火机）

The End