加载中...
题解 CF23C 【Oranges and Apples】

前言

这个题目还是很不错的,我通过这个题目学会了一种解决此类问题的思路,我本来以为是必须要用dp来解决的,但

仔细想想其实还是不必这样的啊。

正文

思路

这个题目的意思是说求出$n$个箱子,使这$n$个箱子的橙子的和与苹果的和可以大于

苹果数与橙子数的一半。所以应该先进行排序,假如$n=3$,那么就有$5$个,

$x_1$ $y_1$$(1)$

$x_2$ $y_2(1)$

$x_3$ $y_3(2)$

$x_4$ $y_4(2)$

$x_5$ $y_5$ 我们要在$y_1$与$y_2$之间挑出比较大的那个数,$y_3$与$y_4$之间挑出比较大的那个数,然后挑最后一个,这样加起来

我们就可以绝对可以保证$x$是足够到一半了,同时我们也调走了最多的y的一半。

代码

```cpp

#include<bits/stdc++.h>
using namespace std;
struct node
{
int a;
int b;
int index;

}ua[2*100000+5];
int cmd(node x,node y)
{
return x.a<y.a;
}
int main()
{

int i,j,k;
int T;
int n;
scanf("%d",&T);
while(T--)
{

    scanf("%d",&n);
    k=2*n-1;
    for(i=1;i<=k;i++)
    {
        scanf("%d%d",&ua[i].a,&ua[i].b);
        ua[i].index=i;
    }
    sort(ua+1,ua+1+k,cmd);
    printf("YES\n");
    for(i=2;i<=k-1;i=i+2)
    {
        if(ua[i].b>ua[i-1].b)
        {
            printf("%d ",ua[i].index);
        }
        else
        {
            printf("%d ",ua[i-1].index);
        }


    }
    printf("%d\n",ua[k].index);

}
return 0;

}

后记:

求点赞和评论QAQ


  目录
劳动
快乐