7-1チェーン時計の重量除去

7-1チェーンテーブルの重量除去(25分)整数キー値付きチェーンテーブルLを指定し、絶対値が繰り返されるキー値ノードを削除する必要があります.すなわち、キー値K毎に、Kに等しい最初の絶対値を有するノードのみが保持される.同時に、削除されたノードはすべて別のチェーンテーブルに保存する必要があります.例えば、Lを21→-15→-15→-7→-15とし、重量除去後のチェーンテーブル21→-15→-7、削除されたチェーンテーブル-15→15を出力する必要があります.
入力フォーマット:第1行にLを与える第1のノードのアドレスと正の整数N(≦100000、ノード総数)を入力します.1つのノードのアドレスは非負の5ビット整数であり、空のアドレスNULLは-1で表される.その後、N行、各行は以下の形式で1つのノードを記述する:アドレスキー値の次のノードアドレスはそのノードのアドレスであり、キー値は絶対値が10000を超えない整数であり、次のノードは次のノードのアドレスである.出力フォーマット:まず、削除されたチェーンテーブルを出力し、削除されたチェーンテーブルを出力します.各ノードは1行を占め、入力したフォーマットで出力されます.サンプルを入力:
00100 5 99999 -7 87654 23854 -15 00000 87654 15 -1 00000 -15 99999 00100 21 23854
出力サンプル:
00100 21 23854 23854 -15 99999 99999 -7 -1 00000 -15 87654 87654 15 -1
まず、構造体a[i]の下付き文字で現在のノードのキー値Keyと次のノードのアドレスNextを格納し、次にflag配列を定義して各キー値Keyの絶対値が重複しているか否かを判断し、そうでなければ、現在のノードをフォーマットで出力し、そうであれば、定義された配列bを実現する中で、重複していると判断されたノードのアドレスを格納するという考え方です.

#include
using namespace std;
const int max = 100100;
struct Node
{
		int Key;
		int Next;
}a[max];
int b[max]//b          
int main()
{
 		int flag[10005];//    
 		memset(flag,0,sizeof(flag))；// 0 
 		int first ,N ,value, m ,add;
 		cin>>first>>N;
 		for(int i=0;i>add；
 			  cin>>a[add].Key>>a[add].Next;
 	    }
 	    m=first;
 	    value=abs(	a[m].Key  )	;//     
 	    printf("%05d %d",first,a[m].Key);
 	     flag[value]=1;//  
 		int   count=0;
 		while(1)
 		{
 		      m=a[m].Next;
	        if(m==-1)//     -1 next               ，     
	        {
	            cout<0)
     {//       
    	printf("%05d %d",b[0],a[b[0]].Key);//       
        for(int i=1;i

テストポイント結果消費時間メモリ0正解2 ms 888 KB 1正解2 ms 896 KB 2正解2 ms 788 KB 3正解139 ms 3588 KB 4正解140 ms 3608 KB
全ACですが、時間が少し長いので、ネットで大神たちのコードを参考にしてみると、やはり高人一等で、時間は前の半分ですね.差が見えてきた!
テストポイント結果消費時間メモリ0正解6 ms 1792 KB 1正解5 ms 1792 KB 2正解6 ms 1792 KB 3正解53 ms 3584 KB 4正解67 ms 3456 KB
オオカミの考え方は,このチェーンテーブルを構造体配列で格納し,大きさはmaxn=100000,node[i]がアドレスiのノードを表す.構造体にnum変数を定義し、num変数を2*maxnに初期化します.num変数の値の最後のsortソートを変更することによってチェーンテーブルの順序を変更します.削除されていないノードのnumをcount 1とマークし、count 1は現在削除されていないノードの個数である.削除するノードのnumをmaxn+count 2と表記し、count 2は現在削除されているノードの個数を表し、最初は2*maxnに初期化されているのでnumをnum=0~maxnは削除しないノード、num=maxn~2 maxnは削除ノード、num=2 maxnは無効ノードとソートすることでsort後に必要な出力順にノードをソートすることができ、前count 1+count 2ノードを出力するだけでいいです

#include
#include 
#include 
#include 
using namespace std;
const int maxn = 100000;
struct NODE 
{
    int address;
    int key;
    int next;
    int num;
}node[maxn];
bool exist[maxn];//          
int cmp1(NODE a, NODE b)
{
    return a.num < b.num;
}
int main() 
{
    int begin, n, count1 = 0, count2 = 0, add;
    scanf("%d%d", &begin, &n);
    for(int i = 0; i < maxn; i++) 
	{
        node[i].num = 2 * maxn;
    }
    for(int i = 0; i < n; i++) 
	{
        scanf("%d", &add);
        scanf("%d%d", &node[add].key, &node[add].next);

        node[add].address = add;
    }
    for(int i = begin; i != -1; i = node[i].next)
    {
        if(exist[abs(node[i].key)] == false) //     
		{
            exist[abs(node[i].key)] = true;
            node[i].num = count1;
            count1++;
        }
        else 
		{
            node[i].num = maxn + count2;
            count2++;
        }
    }
    sort(node, node + maxn, cmp1);
    int count = count1 + count2;
    for(int i = 0; i < count; i++)
	 {
        if(i != count1 - 1 && i != count - 1) 
		{
            printf("%05d %d %05d
", node[i].address, node[i].key, node[i+1].address);
        } 
		else
		{
            printf("%05d %d -1
", node[i].address, node[i].key);
        }
    }
    return 0;
}