首页 > 代码库 > BestCoder Round #4 前两题 hdu 4931 4932

BestCoder Round #4 前两题 hdu 4931 4932

2024-07-17 00:47:01   219人阅读

第一题太水了。。

 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 int a[6]; 7 int main(){ 8     int cas; 9     scanf( "%d", &cas );10     while( cas-- ){11         for( int i = 0; i < 6; i++ ){12             scanf( "%d", &a[i] );13         }14         sort( a, a + 6 );15         int ans1 = a[5] + a[4];16         int ans2 = a[1] + a[2] + a[3];17         if( ans1 > ans2 ) puts( "Grandpa Shawn is the Winner!" );18         else puts( "What a sad story!" );19     } 20          return 0;21 }
View Code

第二题。。呵呵，一个大坑，记得前几次的BC，被hack到哭。。这次做的时候就感觉很怪，开始的时候就是想排序，枚举相邻两个的长度，但是不知道怎么判断符合条件，大神很快就写出代码，但是感觉他的贪心好像有问题，就发了一组数据给他，他发现错误改后又交，又过了pt。。但是始终放心不下，后来在比赛进行到一个半小时的时候就想有没有可能出现小数的数据，最后发现了！！！大神改后我们再交了一发，剩下就把我们测试过的数据准备好来hack别人。。比赛结束后，发现room里只有我过了第二题，全部成功hack，表示不应该手软的，有几个人没有hack到，怕失败了，下次有数据一定不手软。。。

讲一下怎么判断符合条件，a[i]从小到大1 - n，贪心，如果可以的话尽量把线段放在a[i]的左边，用一个pre来记录。。首先，第一个肯定可以把线段放在它的左边，初始化pre = a[1] ,从第2个开始看 if( pre + d <= a[i] ) 说明第i个位置的线段可以放在a[i]的左边，更新pre = a[i]；如果不可以放在左边，那么线段肯定要放在a[i]的右边，if( a[i] + d > a[i+1] )就是说明d不合条件，return false；如果可以放在右边，就更新pre = a[i] + d。。

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6  7 #define mnx 600005 8 #define inf 0x3f3f3f3f 9 10 double a[mnx];11 int n;12 13 bool check( double d ) {14     double pre = a[1];15     for( int i = 2; i < n; ++i ) {16         if( a[i] == pre )17             continue;18         if( pre + d <= a[i] )19             pre = a[i];20         else21             if( a[i] + d > a[i+1] )22                 return 0;23             else24                 pre = a[i] + d;25     }26     return 1;27 }28 int main() {29     int cas;30     scanf( "%d", &cas );31     while( cas-- ) {32         scanf( "%d", &n );33         for( int i = 1; i <= n; ++i )34             scanf( "%lf", &a[i] );35         sort( a + 1, a + n + 1 );36         double ans = 0;37         for( int i = 1; i < n; ++i ) {38             if( check( a[i+1] - a[i] ) )39                 ans = max( ans, a[i+1] - a[i] );40             if( check( ( a[i+1] - a[i] ) / 2 ) )41                 ans = max( ans, ( a[i+1] - a[i] ) / 2 );42         }43         printf( "%.3lf\n", ans * 1.0 );44     }45     return 0;46 }47 //这个是我hack的数据，如果不ac可以试一下这些数据48 /*49 1250 551 -4 1 8 15 2152 353 -1000000000 0 100000000054 5 55 -9 -8 1  10 1256 5 57 -9 0 1 10 1258 559 1 10 -8 12 -960 461 -5 0 100 11162 563 -9 0 11 18 2164 565 -9 0 11 12 2166 467 -1 1 10 1168 669 -1 1 10 16 23 2570 471 1 3 8 1072 673 2 3 8 9 16 1774 answer75 7.00076 1000000000.00077 9.00078 9.00079 9.00080 100.00081 7.00082 9.00083 9.00084 6.00085 5.00086 2.50087 */
View Code

 


联系
我们