贪心WA,求调/证伪
查看原帖
贪心WA,求调/证伪
950927
_luo_gu楼主2024/8/26 19:02
#include <bits/stdc++.h>
#define int long long
using namespace std ;
struct node {
	int x ; 
	int y ; 
	int id ;
}; 
bool cmp1( node a , node b ){
	return a.x > b.x ;
}
bool cmp2( node a , node b ){
	return a.y > b.y ;
}
node a[100005] ;
int n , suma , sumb , numa , numb , cnt ;
bool mar[100005] ;
signed main(){
	scanf("%lld" , &n );
	for( int i = 1 ; i <= n ; i ++ ){
		scanf("%lld" , &a[i].x );
		a[i].id = i ;
		suma += a[i].x ;
	}
	for( int i = 1 ; i <= n ; i ++ ){
		scanf("%lld" , &a[i].y );
		sumb += a[i].y ;
	}
	sort(a+1,a+n+1,cmp1);
	int ii = 1 ;
	cnt = 0 ;
	while( numa*2 <= suma ){
		numa += a[ii].x ;
		numb += a[ii].y ;
		mar[a[ii].id] = true ;
		cnt ++ ;
		ii ++ ; 
	}
	sort(a+1,a+n+1,cmp2);
	ii = 1 ;
	while( numb*2 <= sumb ){
		if( mar[a[ii].id] == false ){
			numb += a[ii].y ;
			mar[a[ii].id] = true ;
			cnt ++ ; 
		}
		ii ++ ;
	}
	printf("%lld\n" , cnt );
	for( int i = 1 ; i <= n ; i ++ ){
		if( mar[i] == true ){
			printf("%lld " , i );
		}
	}
	return 0 ;
}
2024/8/26 19:02
加载中...