L - Median

川长思鸟来 2022-01-29 03:04 215阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY2NzYxMQ_size_16_color_FFFFFF_t_70]  
**Output**

For each test case output one line containing one string of length . If it is possible to assign values to each element so that all the relations are satisfied and the -th element is the median, the -th character of the string should be ‘1’, otherwise it should be ‘0’.

**Sample Input**

2  
5 4  
1 2  
3 2  
2 4  
2 5  
3 2  
1 1  
2 3

Sample Output  
01000  
000

Hint

For the first sample test case, as the 2nd element is smaller than the 1st and the 3rd elements and is larger than the 4th and the 5th elements, it’s possible that the 2nd element is the median.  
For the second sample test case, as the 1st element can’t be larger than itself, it’s impossible to assign values to the elements so that all the relations are satisfied.

题意：n个数，m组数据，这m组数据表示的是 左边的数肯定大于右边的数，但具体是多少不知道，所以通过这m组数据能否判断中位数可能是多少。

思路：floyd传递背包（我也是现学的…）  
先初始化一个二维数组为0，输入l，r 表示l比r大，map\[l\]\[r\]=1 说明此路可以，并且l>r,  
遍历所有节点，更新所有可能到达的值，比如 1->2 2->4 ,此时1也可以到达4 ，更新map【1】【4】=1 表示1也比4大（1比2大，2比4大，通过传递性，1也比4大）。  
用flag标记下特殊值，如果l==r或map\[l\]\[r\]==1&&map\[r\]\[l\]==1,这两种情况是矛盾的，所以输出0。  
用in数组统计n个点的入度了多少次（也就是有多少个数比i小）  
用out数组统计n个点的出度了多少次（也就是有多少个数比i大） 画个图很好理解。

他让求可能是中位数的值，想一想，n个数（n是个奇数），中位数肯定是在（n+1）/2的位置。  
如果他不是中位数，他的入度或者出度的数肯定>=（n+1）/2  
因为n个数（n是奇数），比中位数大的有（n+1）/2-1个 比中位数小的也有（n+1）/2-1个  
所以通过数量来判断是否可能为中位数。

AC代码：

#include<iostream>
    #include<cstring>
    #include<cmath>
    using namespace std;
    typedef long long ll;
    int map[105][105],in[105],out[105];
    int init()
    {
    	for(int i=1;i<=105;i++)
    	{ 
    		in[i]=0;
    		out[i]=0;
    		for(int j=1;j<=100;j++)
    		{
    			map[i][j]=0;
    		}
    	}
    }
    int main()
    {
    	ll t;
    	cin>>t;
    	while(t--)
    	{	
    		init();
    		ll n,m;
    		cin>>n>>m;
    		ll flag=0; 
    		for(int i=1;i<=m;i++)
    		{
    			ll l,r;
    			cin>>l>>r;
    			map[l][r]=1;
    			if(l==r)
    				flag=1;
    		}
    		for(int k=1;k<=n;k++)
    		{
    			for(int i=1;i<=n;i++)
    			{
    				for(int j=1;j<=n;j++)
    				{
    					if(map[i][k]&&map[k][j])
    						map[i][j]=1;
    				}
    			}
    		}
    		for(int i=1;i<=n;i++)
    		{
    			for(int j=1;j<=n;j++)
    			{
    				if(map[i][j]==1&&map[j][i]==1)
    				{
    					flag=1;
    				}	
    			}
    		}
    		for(int i=1;i<=n;i++)
    		{
    			for(int j=1;j<=n;j++)
    			{
    			
    				if(map[i][j]==1)
    				{
    					in[i]++;
    					out[j]++;
    				}
    			}
    		}
    		if(flag)
    		{
    			for(int i=1;i<=n;i++)
    			{
    				cout<<"0";
    			}
    			cout<<endl;
    		}
    		else
    		{
    			for(int i=1;i<=n;i++)
    			{
    				if(in[i]>=(n+1)/2||out[i]>=(n+1)/2)
    					cout<<"0";
    				else
    					cout<<"1";
    			}
    			cout<<endl;
    		}	
    	}
    	return 0;
     }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY2NzYxMQ_size_16_color_FFFFFF_t_70]: /images/20220129/99557fe15bd040bab71fb4afa081ca92.png